sundeepblue
4/27/2014 - 12:28 PM

make a left right sibling tree. You are given a complete tree, with left and right pointers set as usual but there are another two pointer i

make a left right sibling tree. You are given a complete tree, with left and right pointers set as usual but there are another two pointer in the "node" named "left_sibling" and "right_sibling". Write a function to set the sibling pointers to their respective values

connect silbing.cpp
content_copyfile_download
struct TreeNode {
    int val;
    TreeNode *left, *right, *lsb, *rsb;
};

// not tested
TreeNode* connect(TreeNode* root) {
    if(!root) return NULL;
    if(!root->left && !root->right) return root;
    
    TreeNode *L = connect(root->left);
    TreeNode *R = connect(root->right);

    TreeNode *pL = L, *pR = R;
    while(pL && pR) {
        pL->rsb = pR;
        pR->lsb = pL;
        pL = pL->right;
        pR = pR->left;
    }
    return root;
}