Reverse alternate levels of a binary tree

Problem:
Given a Binary Tree, reverse the alternate level nodes of the binary tree.

Given tree: 
               a
            /     \
           b       c
         /  \     /  \
        d    e    f    g
       / \  / \  / \  / \
       h  i j  k l  m  n  o 

Modified tree:
          a
            /     \
           c       b
         /  \     /  \
        d    e    f    g
       / \  / \  / \  / \
      o  n m  l k  j  i  h

Solution:

A simple solution is to do following steps.
1) Access nodes level by level.
2) If current level is odd, then store nodes of this level in an array.
3) Reverse the array and store elements back in tree.

A tricky solution is to do two inorder traversals. Following are steps to be followed.
1) Traverse the given tree in inorder fashion and store all odd level nodes in an auxiliary array. For the above example given tree, contents of array become {h, i, b, j, k, l, m, c, n, o}

2) Reverse the array. The array now becomes {o, n, c, m, l, k, j, b, i, h}

3) Traverse the tree again inorder fashion. While traversing the tree, one by one take elements from array and store elements from array to every odd level traversed node.
For the above example, we traverse ‘h’ first in above array and replace ‘h’ with ‘o’. Then we traverse ‘i’ and replace it with n.

Note that the solution works for complete binary trees only. Perhaps it could be modified to work with incomplete trees too, by storing "empty" elements in the array on step #1.

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.geeksforgeeks.org/reverse-alternate-levels-binary-tree/

Inorder traversal of binary tree w/o recursion

Problem:
Inorder traversal of binary tree w/ recursion

Solution:

/* Iterative method using stack */
Inordertraversal(struct btree *root)   
{
 while(1)
 {   
  while( root )
  {
   push(root);
   root = root->left;
  }
  if(Isstackempty(S))
   return;
  printf( S(top)->data);
  root = pop(S);
  root = root->right;
 }
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=5198302274387968

LCA or Lowest Common Ancestor of a Binary Tree

Problem:
Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

E.g.:

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

In this tree, an LCA for 6 and 4 is 5. For 5 and 4 it is 5,too. For 7 and 1 it is 3. And so on.

Solution:
A Bottom-up Approach:
We traverse from the bottom, and once we reach a node which matches one of the two nodes, we pass it up to its parent. The parent would then test its left and right subtree if each contain one of the two nodes. If yes, then the parent must be the LCA and we pass its parent up to the root. If not, we pass the lower node which contains either one of the two nodes (if the left or right subtree contains either p or q), or NULL (if both the left and right subtree does not contain either p or q) up.

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

Complexity:

time - O(n)
space - O(log n)

Links and credits:
http://leetcode.com/2011/07/lowest-common-ancestor-of-a-binary-tree-part-i.html

Binary Tree Zigzag Level Order Traversal

Problem:
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

Solution:
This problem can be solved easily using two stacks (one called currentLevel and the other one called nextLevel). You would also need a variable to keep track of the current level's order (whether it is left->right or right->left).

You pop from stack currentLevel and print the node's value. Whenever the current level's order is from left->right, you push the node's left child, then its right child to stack nextLevel. Remember a Stack is a Last In First OUT (LIFO) structure, so the next time when nodes are popped off nextLevel, it will be in the reverse order.

On the other hand, when the current level's order is from right->left, you would push the node's right child first, then its left child. Finally, don't forget to swap those two stacks at the end of each level (ie, when currentLevel is empty).

void printLevelOrderZigZag(BinaryTree *root) {
    stack<BinaryTree*> currentLevel, nextLevel;
    bool leftToRight = true;
    currentLevel.push(root);
    while (!currentLevel.empty()) {
        BinaryTree *currNode = currentLevel.top();
        currentLevel.pop();
        if (currNode) {
            cout << currNode->data << " ";
            if (leftToRight) {
                nextLevel.push(currNode->left);
                nextLevel.push(currNode->right);
            } else {
                nextLevel.push(currNode->right);
                nextLevel.push(currNode->left);
            }
        }
        if (currentLevel.empty()) {
            cout << endl;
            leftToRight = !leftToRight;
            swap(currentLevel, nextLevel);
        }
    }
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://discuss.leetcode.com/questions/52/binary-tree-zigzag-level-order-traversal

Print Left View of a Binary Tree

Problem:
Given a Binary Tree, print left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from left side. Left view of following tree is 12, 10, 25.

          12
       /     \
     10       30
            /    \
          25      40

Solution:
The left view contains all nodes that are first nodes in their levels. A simple solution is to do level order traversal and print the first node in every level.

The problem can also be solved using simple recursive traversal. We can keep track of level of a node by passing a parameter to all recursive calls. The idea is to keep track of maximum level also. Whenever we see a node whose level is more than maximum level so far, we print the node because this is the first node in its level (Note that we traverse the left subtree before right subtree).

Note: the same procedure can be used to get the "right view" of a tree if we first traverse the right sub-tree in the recursive algorithm.

// Recursive function to print left view of a binary tree.
void leftViewUtil(struct node *root, int level, int *max_level)
{
    // Base Case
    if (root==NULL)  return;
 
    // If this is the first node of its level
    if (*max_level < level)
    {
        printf("%d\t", root->data);
        *max_level = level;
    }
 
    // Recur for left and right subtrees
    leftViewUtil(root->left, level+1, max_level);
    leftViewUtil(root->right, level+1, max_level);
}
 
// A wrapper over leftViewUtil()
void leftView(struct node *root)
{
    int max_level = 0;
    leftViewUtil(root, 1, &max_level);
}

Complexity:

time - O(n)
space - O(n)

Links and credits:
http://www.geeksforgeeks.org/print-left-view-binary-tree/

Print Postorder traversal from given Inorder and Preorder traversals

Problem:
Given Inorder and Preorder traversals of a binary tree, print Postorder traversal.

Example:

Input:
Inorder traversal in[] = {4, 2, 5, 1, 3, 6}
Preorder traversal pre[] = {1, 2, 4, 5, 3, 6}

Output:
Postorder traversal is {4, 5, 2, 6, 3, 1}

Trversals in the above example represents following tree

         1
      /     \   
     2       3
   /   \      \
  4     5      6

Solution:
A naive method is to first construct the tree, then use simple recursive method to print postorder traversal of the constructed tree. We can print postorder traversal without constructing the tree.

1. The pre[0] is the root of the tree --> 1
2. The in[] represents the tree as:
   
   { { left-sub-tree } ;  root ;   { right-sub-tree } }
   
   So the index of the root at in[] is the length of the left sub-tree --> 3
3. The (in[].length - rootIndex - 1) is the length of the right sub-tree --> 2
4. The pre[] represents the tree as:
   
   { root ;   { left-sub-tree } ;  { right-sub-tree } }
   
   Since we know the lengths of the sub-trees from steps #2 and #3, we can proceed recursively as follows:
   
   leftIn[] = in[ 0 .. (rootIndex-1) ] = { 4, 2, 5 }
   leftPre[] = pre[ 1 .. (rootIndex-2) ] = { 2, 4, 5 }
   
   rightIn[] = in[ (rootIndex+1) .. (length-1) ] = { 3, 6 }
   rightPre[] = pre[ (rootIndex+1) .. (length-1) ] = { 3, 6 }
   
   Recursion ends when the lengths of the in[] and pre[] become equal to 1.

int search(int arr[], int x, int n)
{
    for (int i = 0; i < n; i++)
      if (arr[i] == x)
         return i;
    return -1;
}
 
// Prints postorder traversal from given inorder and preorder traversals
void printPostOrder(int in[], int pre[], int n)
{
   // The first element in pre[] is always root, search it
   // in in[] to find left and right subtrees
   int root = search(in, pre[0], n);
 
   // If left subtree is not empty, print left subtree
   if (root != 0)
      printPostOrder(in, pre+1, root);
 
   // If right subtree is not empty, print right subtree
   if (root != n-1)
      printPostOrder(in+root+1, pre+root+1, n-root-1);
 
   // Print root
   cout << pre[0] << " ";
}

Complexity:

time - O(n^2)
space - O(n)

Links and credits:
http://www.geeksforgeeks.org/print-postorder-from-given-inorder-and-preorder-traversals/

Populating Next Right Pointers in Each Node

Problem:
Given a binary tree

struct TreeLinkNode {
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.

Note:
You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL

Solution:

public void connect(TreeLinkNode root) {

    TreeLinkNode leftWall = root;
    while (leftWall != null) {

        TreeLinkNode across = leftWall;
        while (across != null) {
            if (across.left != null) {
                across.left.next = across.right;
            }

            if (across.right != null && across.next != null) {
                across.right.next = across.next.left;
            }

            across = across.next;
        }
        leftWall = leftWall.left;
    }
}

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://discuss.leetcode.com/questions/7/populating-next-right-pointers-in-each-node

Construct a binary tree from inorder and preorder traversals

Problem:
Construct a BST from inorder and preorder traversal string

Solution:

Let us consider the below traversals:

Inorder sequence: D B E A F C
Preorder sequence: A B D E C F

In a Preorder sequence, leftmost element is the root of the tree. So we know ‘A’ is root for given sequences. By searching ‘A’ in Inorder sequence, we can find out all elements on left side of ‘A’ are in left subtree and elements on right are in right subtree. So we know below structure now.

                 A
               /   \
             /       \
           D B E     F C

We recursively follow above steps and get the following tree.

         A
       /   \
     /       \
    B         C
   / \        /
 /     \    /
D       E  F

struct node* buildTree(char in[], char pre[], int inStrt, int inEnd)
{
  static int preIndex = 0;
 
  if(inStrt > inEnd)
     return NULL;
 
  /* Pick current node from Preorder traversal using preIndex
    and increment preIndex */
  struct node *tNode = newNode(pre[preIndex++]);
 
  /* If this node has no children then return */
  if(inStrt == inEnd)
    return tNode;
 
  /* Else find the index of this node in Inorder traversal */
  int inIndex = search(in, inStrt, inEnd, tNode->data);
 
  /* Using index in Inorder traversal, construct left and
     right subtress */
  tNode->left = buildTree(in, pre, inStrt, inIndex-1);
  tNode->right = buildTree(in, pre, inIndex+1, inEnd);
 
  return tNode;
}

Complexity:

time - O(n^2)
space - O(n)

Links and credits:
http://www.careercup.com/question?id=21296665
http://www.geeksforgeeks.org/construct-tree-from-given-inorder-and-preorder-traversal/
http://discuss.leetcode.com/questions/148/construct-binary-tree-from-preorder-and-inorder-traversal

Check if a binary tree is symmetric

Problem:
Check if a given binary tree is symmetric.

Solution:

public boolean recurseSymmetry(Node<AnyType> left, Node<AnyType> right ){
   if(left == null || right == null) return left==right;
   else 
      return left.value == right.value &&
             recurseSymmetry(left.left, right.right) &&
             recurseSymmetry(left.right, right.left);
}

Complexity:

time - O(n)
space - O(n) (for recursion stack)

Links and credits:
http://www.careercup.com/question?id=20884671

Inorder Tree Traversal without recursion and without stack (Morris Traversal)

Problem:
Traverse a binary tree without using stack and recursion.

Solution:
Using Morris Traversal, we can traverse the tree without using stack and recursion. The idea of Morris Traversal is based on Threaded Binary Tree. In this traversal, we first create links to Inorder successor and print the data using these links, and finally revert the changes to restore original tree.

1. Initialize current as root 
2. While current is not NULL
   If current does not have left child
      a) Print current’s data
      b) Go to the right, i.e., current = current->right
   Else
      a) Make current as right child of the rightmost node in current's left subtree
      b) Go to this left child, i.e., current = current->left

void MorrisTraversal(struct tNode *root)
{
  struct tNode *current,*pre;
 
  if(root == NULL)
     return; 
 
  current = root;
  while(current != NULL)
  {                 
    if(current->left == NULL)
    {
      printf(" %d ", current->data);
      current = current->right;      
    }    
    else
    {
      /* Find the inorder predecessor of current */
      pre = current->left;
      while(pre->right != NULL && pre->right != current)
        pre = pre->right;
 
      /* Make current as right child of its inorder predecessor */
      if(pre->right == NULL)
      {
        pre->right = current;
        current = current->left;
      }
             
      /* Revert the changes made in if part to restore the original 
        tree i.e., fix the right child of predecssor */   
      else 
      {
        pre->right = NULL;
        printf(" %d ",current->data);
        current = current->right;      
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
}

Complexity:

time - O(n)
space - O(1)

Links and credits:
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/
http://www.careercup.com/question?id=6154593645887488

Check if the given binary tree is BST or not

Problem:
Check if the given binary tree is BST or not.

Solution:

public boolean isBSTMain(Node root) {
 return (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}

private boolean isBST(Node node, int min, int max) {
 if (node == null)  return true;
 
 if (node.data < min || node.data > max) return false;

 // left should be in range min...node.data
 boolean leftOk = isBST(node.left, min, node.data);
 if (!leftOk) return false;

 // right should be in range node.data..max
 return isBST(node.right, node.data, max);
}

Complexity:

time - O(n)
space - O(n) (the stack space for the recursion)

Links and credits:
http://www.careercup.com/question?id=19685712