Fill in the sibling pointer in the binary tree

You are given a binary tree which has a sibling pointer in addition to left and right pointer. The tree has left and right child set correctly but sibling pointer is not yet set. Your task is to traverse the tree and fill in the sibling pointer. A sibling is defined as a node next to the given node at the same level.

In the tree above B and C, and D and E are siblings. So sibling pointer of B should point to C and sibling pointer of D should point to E. Sibling pointer of C and E should be null because they don't have any siblings to the right.

This problem is easily solved using level order traversal as shown below.

class Node {
public:
    Node *left;
    Node *right;

    // Sibling pointer that needs to be set
    Node *sibling;

    // Value stored in the node. For simplicity

    // we assume name to be the value
    std::string name;
};

// Fill in the sibling pointer of a binary tree
void fill_node_with_next_sbiling(Node *node) {
    if (!node)
        return;

    // Initialize the queue with the root node.
    std::queue<node> queue;
    queue.push(node);

    // Set count of current level in the queue to 1.
    int cur_count = 1;
    int child_count = 0;

    Node *prev = NULL;

    while (!queue.empty()) {
        Node *n = queue.front();
        queue.pop();

        // Set the sibling pointer and set previous as current node
        if (prev) {
            prev->sibling = n;
            prev = n;
        } else {
            prev = n;
        }

        cur_count--;

        if (n->left != NULL) {
            queue.push(n->left);
            child_count++;
        }

        if (n->right != NULL) {
            queue.push(n->right);
            child_count++;
        }

        // All nodes in the current level are done.
        // Set the cur_count to next level count 
        // for processing next level
        if (cur_count == 0) {
            cur_count = child_count;
            child_count = 0;
            prev = NULL;
        }

    }
}

Iterative Inorder Traversal

Iterative inorder traversal is a little complicated than Preorder traversal. As for Preorder we need to use stack for Inorder traversal as well but the nodes can't be removed from stack until it's children are pushed to the stack and the node has been visited. For all nodes we need to push their children on the stack first before visiting it. We mark whether the children have been put into stack or not for a node my using another stack call marks. When adding children to the stack we set mark to true on the marks stack. Now when we pop the node again we check corresponding mark and if it is set to true we know that it's children has already been processed. Thus we visit the node (print the value in the code below). In Inorder traversal left child, parent and right child are processed respectively. So while pushing on the stack we do it on the reverse order so that Inorder requirements are maintained.

  
void inorder_traversal(Node *root) {
 if(root == 0)
  return;

 std::vector<bool> marks;
 std::vector<Node*>nodes;
 nodes.push_back(root);
 marks.push_back(false);

 while(!nodes.empty()){

//read the top mark
  bool mark = marks.back();
  marks.pop_back();

 //read the top node
  Node *node = nodes.back();
  nodes.pop_back();
 
 if(mark) {
 //if mark is set then the node is visited
   std::cout << node->value_ << std::endl;
  }
  else {
 //put the righ child on stack
   if(node->right_ != NULL) {
    nodes.push_back(node->right_);
    marks.push_back(false);
   }

 //set mark to true
 //put the node in the stack
   marks.push_back(true);
   nodes.push_back(node);

 //put left child on the stack
   if(node->left_ != NULL) {
    nodes.push_back(node->left_);
    marks.push_back(false);
   }
  }
 }
}
 

Iterative Preorder Traversal

Preorder traversal is easy when you consider recursive approach but it's quite tricky without recursion. The idea is to simulate recursion using stack. Start from the root and put the root's right and left child on the stack respectively. Then pop the topmost element from the stack, visit it and then again put it's right and left child on the stack if they exists. Continue this till the stack is empty.

  
void preorder_traversal(Node *root) {
 if(root == 0)
  return;

 std::vector stack;
 stack.push_back(root);
 Node *current;
 
 while ( !stack.empty()) {
  current = stack.back();
  stack.pop_back();
  
  std::cout << current->value_ << std::endl;
  
  if(current->right_ != NULL)
   stack.push_back(current->right_);
  if(current->left_ != NULL)
   stack.push_back(current->left_);
 }
}

Binary tree reconstruction from IN and PRE or POST order traversals

Reconstructing binary tree from Inorder and Preorder traversal is pretty straighforward. The idea is to number the Inorder sequence in increasing order and use that number as a key to insert into Binary Search Tree. The insertion into BST is carried out in the order given in Preorder traversal.

Example:
Inorder: DBEAFCG
Preorder: ABDECFG

Now number the inorder traversal:DBEAFCG (1234567). Thus the preorder traversal will be ABDECFG (4213657)

Insert the items picking them in preorder into BST. So first you will insert 4(A), then 2(B), 1(D) and so on. This will give you the original tree from which traversals are generated.

Code for it is given below

//Tree node
class Node {

public Node left;
public Node right;

//key
public int key;

//label of the node
public char label;

public Node(Node left, Node right, int key, char label){
this.left = left;
this.right = right;
this.value = val;
this.key= key;
}


public Node(int key, char label) {
this(null, null, key,label);
}


}

//Binary Search Tree
class Tree {
public Node root;

public Tree() {
this(null);
}
public Tree(Node root) {
this.root = root;
}


public void insert(int key, char label) {

Node node = new Node(key, label);
if(root == null) {
root = node;
return;
}

Node temp = root;
Node parent = root;

while(temp != null) {
parent = temp;
if ( key < temp =" temp.left;" temp ="=" left =" node;" temp =" temp.right;" temp ="=" right =" node;" table =" new" count =" 0;" bst =" new">

Reconstruction from Inorder and Postorder

Steps are pretty much the same for Postorder too. But while inserting into BST we start from last element of the traversal and continue on to first.