Binary Tree Vertical Order Traversal

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Examples:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its vertical order traversal as:

[
  [9],
  [3,15],
  [20],
  [7]
]

Given binary tree [3,9,20,4,5,2,7],

    _3_
   /   \
  9    20
 / \   / \
4   5 2   7

return its vertical order traversal as:

[
  [4],
  [9],
  [3,5,2],
  [20],
  [7]
]

Starting from root, given a node a label i, then it's left child (if not null) has a label i - 1 and it's right child (if not null) has a label i + 1. Traverse the tree using level order traversal and group all the nodes with the same label together.

public class VerticalOrderTraversal {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> rst = new ArrayList<>();
        if (root == null) {
            return rst;
        }

        Queue<TreeColumnNode> queue = new LinkedList<>();
        queue.add(new TreeColumnNode(root, 0));
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        Map<Integer, List<Integer>> labelSet = new HashMap<>();
        while (!queue.isEmpty()) {
            TreeColumnNode curr = queue.poll();
            if (!labelSet.containsKey(curr.label)) {
                labelSet.put(curr.label, new ArrayList<>());
            }
            labelSet.get(curr.label).add(curr.node.val);
            min = Math.min(curr.label, min);
            max = Math.max(curr.label, max);
            if (curr.node.left != null) {
                queue.add(new TreeColumnNode(curr.node.left, curr.label - 1));
            }
            if (curr.node.right != null) {
                queue.add(new TreeColumnNode(curr.node.right, curr.label + 1));
            }
        }
        for (int i = min; i <= max; i++) {
            rst.add(labelSet.get(i));
        }
        return rst;
     }

    private class TreeColumnNode {
        TreeNode node;
        int label;
        public TreeColumnNode(TreeNode node, int label) {
            this.node = node;
            this.label = label;
        }
    }
}

All the Tree Traversal you need (not recursively!) Too

I got this idea of going through Leetcode again to learn Python in a more fun way. The first thing is basic data structures, and we definitely cannot forget binary tree.

Here are all the tree traversal solutions. All solutions are accepted on Leetcode. I only include the recursive version for the preorder traversal, since all others are similar and trivial.

If you need the Java version, see here.

Enjoy. :)


Preorder

The recursive way has two versions, the first one uses two functions while the second one use a nested recursive function inside the global one. See here for my post about the nested function in Python.

def preOrder(root):
    """
    iterative version
    :param root:
    :return:
    """
    rst = []
    if not root:
        return rst
    stack = [root]
    while stack:
        curr = stack.pop()
        if curr.right is not None:
            stack.append(curr.right)
        if curr.left is not None:
            stack.append(curr.left)
        rst.append(curr.val)
    return rst

def preOrderRec(root):
    """
    recursive version
    :param root:
    :return:
    """
    rst = []
    preorderHelper(root, rst)
    return rst

def preorderHelper(root, rst):
    if root is not None:
        rst.append(root.val)
        preorderHelper(root.left, rst)
        preorderHelper(root.right, rst)


def preOrderRec2(root):
    """
    nested inner recursive function
    :param root:
    :return:
    """
    rst = []

    def recursion(root):
        if root:
            rst.append(root.val)
            recursion(root.left)
            recursion(root.right)
    recursion(root)
    return rst

Inorder:

def inOrder(root):
    """
    in order traversal, iterative
    use a stack
    :param root:
    :return:
    """
    rst = []
    if not root:
        return rst
    stack = []
    while root or stack:
        if root:
            stack.append(root)
            root = root.left
        else:
            root = stack.pop()
            rst.append(root.val)
            root = root.right
    return rst

Postorder:
This one is quite different from the Java version. Since Python does not have any peek() method for the list class, I cannot use the way I used in the Java version (Actually, there is a way: use a deque, popleft() first and then appendleft(), but I don't think it's quite efficient).
In Python, I used two stacks. Basically, it looks like this:

1. append the root to the first stack
2. pop the root out the first stack and append it to the second stack
3. append the left child followed by the right child of the root (if any exists)
4. repeat 2 and 3 until the first stack is empty
5. pop the nodes in the second stack and append it to the result list

Below the Python version is the Java version using the conventional method, you can compare the two method. :)

def postOrder(root):
    """
    iterative way, using two stacks
    :param root:
    :return:
    """
    rst = []
    if not root:
        return rst
    stack1 = [root]
    stack2 = []
    while stack1:
        curr = stack1.pop()
        if curr.left is not None:
            stack1.append(curr.left)
        if curr.right is not None:
            stack1.append(curr.right)
        stack2.append(curr)
    while stack2:
        rst.append(stack2.pop().val)
    return rst

Java version:

public ArrayList postorderTraversal(TreeNode root) {
        ArrayList rst = new ArrayList();
        if (root == null)
            return rst;
        Stack stack = new Stack();
        TreeNode curr = null;
        TreeNode prev = null;
        stack.push(root);
        while (!stack.empty())
        {
            curr = stack.peek();
            //prev == null, root
            //traverse down
            if (prev == null || prev.left == curr || prev.right == curr)
            {
                if (curr.left != null)
                    stack.push(curr.left);
                //need to traverse to the bottom of the tree first before goes to the right side
                else if (curr.right != null)
                    stack.push(curr.right);
            }
            // here comes the right side
            else if (curr.left == prev)
            {
                if (curr.right != null)
                    stack.push(curr.right);
            }
            //finally we can add nodes
            else
            {
                rst.add(curr.val);
                stack.pop();
            }
            prev = curr;
        }
        return rst;
    }

Level order:

from collections import deque

def levelOrder(root):
    """
    level order traversal
    :param root:
    :return:
    """
    rst = []
    if not root:
        return rst
    q = deque([root])
    while q:
        size = len(q)
        level = []
        for i in range(size):
            curr = q.popleft()
            if curr.left is not None:
                q.append(curr.left)
            if curr.right is not None:
                q.append(curr.right)
            level.append(curr.val)
        rst.append(level)
    return rst

Zigzag level order:

def zigzag(root):
    rst = []
    if not root:
        return rst
    thisLevel = [root]
    reverse = True
    while thisLevel:
        nextLevel = []
        level = []
        while thisLevel:
            curr = thisLevel.pop()
            level.append(curr.val)
            if reverse:
                if curr.left is not None:
                    nextLevel.append(curr.left)
                if curr.right is not None:
                    nextLevel.append(curr.right)
            else:
                if curr.right is not None:
                    nextLevel.append(curr.right)
                if curr.left is not None:
                    nextLevel.append(curr.left)

        thisLevel = nextLevel
        reverse = not reverse
        rst.append(level)
    return rst

Diameter of a tree

My last post pumped me to calculate the diameter of a tree. And there is actually the question: 

The diameter of a tree is the number of nodes on the longest path between two leaves in the tree. The diagram below shows a tree with diameter nine, the leaves that form the ends of a longest path are shaded (note that there is more than one path in each tree of length nine, but no path longer than nine nodes).
In particular, note that the diameter of a tree T is the largest of the following quantities:
the diameter of T's left subtree
the diameter of T's right subtree
the longest path between leaves that goes through the root of T
Given the root node of the tree, return the diameter of the tree

public static int maxDepth(TreeNode root){
  if(root == null)
   return 0;
  if(root.left == null && root.right == null)
   return 1;
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
 }
 public static int Diameter(TreeNode root){
  if(root == null)
   return 0;
  if(root.left == null && root.right == null)
   return 1;
  return Math.max(Math.max(Diameter(root.left), Diameter(root.right)), maxDepth(root.left) + maxDepth(root.right));
 }

Suffix tree

A suffix tree, as its name, is a tree that contains all the suffixes of a given string. Implementation of a suffix allows linear time to search for the substring of a given string.

The implementation of suffix tree can be various, I use the version provided on Cracking the coding interview. Since everyone likes "banana", to illustrate, I am also using "banana" as an example.

There are two data structures used in TreeNode: a list that tracks the indices of the first character of all substrings of the given string, and a map of all children of a given tree node. The key is the the current character and the value is a child tree node. A child node can only have one unique value, that is a character, but the index list contains all indexes the character occurs in the tree.

Insertion: 
Insert the index of the current character, if there exists a child node with the same value (character), get the child and recursively add the index and the substring of the current string into the child node.
If not, initialize a new child node and recursively add the index and the substring to the child node.

Search: 
If the string contains the input substring, it will return a list that contains all starting indices of the substring, otherwise it will return null. To implement this, we recursively search if all characters in the input string are children of the root node, and return the list if we parse to the end of the string.

Construct the tree:
Simply insert all substrings of the string to the root node.

public class SuffixTree {
 TreeNode root = new TreeNode();
 public SuffixTree(String s){
  for(int i = 0; i < s.length(); i++)
   root.insert(s.substring(i), i);
 }
 public List getIndexes(String s){
  return root.getIndexes(s);
 }

}
public class TreeNode {
 Map children;
 char value;
 List indexes;
 public TreeNode(){
  children = new HashMap();
  //track the start index of the substring
  indexes = new ArrayList();
 }
 public void insert(String s, int index){
  indexes.add(index);
  if(s != null && s.length() > 0){
   value = s.charAt(0);
   TreeNode child = null;
   if(children.containsKey(value))
    child = children.get(value);
   else{
    child = new TreeNode();
    children.put(value, child);
   }
   child.insert(s.substring(1), index);
   System.out.println(information());
  }
 }
 public List getIndexes(String s){
  if(s == null || s.length() == 0){
   return indexes;
  }
  else{
   char first = s.charAt(0);
   if(children.containsKey(first)){
    return children.get(first).getIndexes(s.substring(1));
   }
  }
  return null;
 }
}

Red-black Tree: A self - balanced tree

A red-black tree is a binary search tree in which each node is colored red or black such that

• The root is black
• The children of a red node are black
• Every root to leaf path has the same number of black nodes

Red-black tree do not necessarily have minimum height, but the height is never greater than 2 log(n), so it guarantees searching in O(log n) time. 

Let B be the number of black nodes in the shortest possible root to leaf path. Longer possible paths may be constructed by inserting red nodes ( since every path must have same number of black nodes). However, it is impossible to have two consecutive red nodes since the children of a red node must be black, thus the longest possible path consists of 2B nodes, alternating black and red. 

The helper methods

Since we will construct a self balanced tree, it is highly possible that when we insert or delete a node, the tree will be imbalanced, thus we need some methods to reconstruct the tree. 

Rotate right

This method is needed when we have two consecutive red nodes on the left. Since there is the rule that any red parents must have two black children, we need to rotate the tree to satisfy the rule. 

private ColoredTreeNode rotateRight(ColoredTreeNode node){
  ColoredTreeNode x = node.left;
  node.left = x.right;
  x.right = node;
  x.color = x.right.color;
  x.right.color = Color.red;
  x.numSubtree = node.numSubtree;
  node.numSubtree = size(node.left) + size(node.right) + 1;
  return x;
 }

 Rotate Left

Update 2015 - 04 01:
This method is actually used when you insert a node to the right, especially when the root is red, or the root doesn't contain a left child, this node will balance the tree.


This method is used when the left child is black and the right child is red. The reason to perform this method is that since this is a left leaning tree, we want the left subtree to always be deeper than right subtree (if not equal to). Note that we don't really care if the parent is red or black. The following figure shows if we have a black parent. If we have a red parent, there is always a black parent of that red parent since the root of the tree is black, so after rotation, we will have two consecutive red left nodes, when we return to the parent's (the red one) parent (the black one), it will rotate right to maintain the correct order.

private ColoredTreeNode rotateLeft(ColoredTreeNode node){
  ColoredTreeNode x = node.right;
  node.right = x.left;
  x.left = node;
  x.color = x.left.color;
  x.left.color = Color.red;
  x.numSubtree = node.numSubtree;
  node.numSubtree = size(node.left) + size(node.right) + 1;
  return x;
 }

Flip node
If both nodes are red, since next time we will add a red node, in order to reduce the re-construct steps, we flip the nodes and make leaf nodes black.

private void flipColors(ColoredTreeNode node){
  node.color = node.color == Color.red ? Color.black : Color.red;
  node.left.color = node.left.color == Color.red ? Color.black : Color.red;
  node.right.color = node.right.color == Color.red ? Color.black : Color.red; 
 }

Move Red Left
This method is used for deleting nodes. Assuming the node is red (we may set the root node to red if needed, see Deletion code below), if the node's left child and the left child's left child are both black, we move the node to the left.

private ColoredTreeNode moveRedLeft(ColoredTreeNode node){
  flipColors(node);
  if(isRed(node.right.left)){
   node.right = rotateRight(node.right);
   node = rotateLeft(node);
   flipColors(node);
  }
  return node;
 }

Move Red Right
This method is also used for deleting nodes. Assuming the node is red, if the node's right child and the right child's left child are both black, move the red node to the right.

private ColoredTreeNode moveRedRight(ColoredTreeNode node){
  flipColors(node);
  if(isRed(node.left.left)){
   node = rotateRight(node);
   flipColors(node);
  }
  return node;
 }

Search
Search a node follows the same rule as that in searching in a BST, since red-black tree is a BST.

public boolean contains(Comparable k) {
  return get(k) != null;
 }
 public Object get(Comparable key){
  return get(root, key);
 }
 private Object get(ColoredTreeNode node, Comparable k){
  while(node != null){
   int cmp = node.key.compareTo((T)k);
   if(cmp > 0) node = node.left;
   else if(cmp < 0) node = node.right;
   else return node.data;
  }
  return null;
 }

Insertion

1. The insertion to the tree first follows the traditional BST insertion rule, but color the newly inserted node to red. 
2. Since the children of a red node are black, if the parent of the node you've just inserted is red, you will have to readjust the color.
3. In case after you readjust the tree, the root of the tree is not black, color the root to black.

public void insert(Comparable k, Object obj){
  root = insert(k, obj, root);
  //System.out.println(root.key);
  root.color = Color.black;
 }
 private ColoredTreeNode insert(Comparable k, Object obj, ColoredTreeNode root){
  if(root == null){
   //System.out.println("Inserted new node!");
   return new ColoredTreeNode(k, obj, Color.red, 1);
  }
  int cmp = k.compareTo((T)root.key);
  if(cmp < 0)
   root.left = insert(k, obj, root.left);
  else if (cmp > 0)
   root.right = insert(k, obj, root.right);
  else
   root.data = obj;
  /*
   * rotate and re-adjust color
   */
  //the new added node is the right child 
  //of the root, since the tree is left leaning
  //we need to left rotate the tree
                //moreover, it can make the leaf node black
  if(isRed(root.right) && !isRed(root.left))
   root = rotateLeft(root);
  //two consecutive red nodes, rotate right
  if(isRed(root.left) && isRed(root.left.left))
   root = rotateRight(root);
  //a red node must have two black children
  //flip the color if a node have two red children
  //if the parent is black, and the parent's parent is 
  //red, flip the nodes will cause two red parents on the 
  //left, and the tree will rotate right to correct it
  if(isRed(root.left) && isRed(root.right))
   flipColors(root);
  root.numSubtree = size(root.left) + size(root.right) + 1;
  return root; 
 }

Deletion
Deletion is a little bit more complicated, I am going to use some illustrations.

1. Delete the left most leaf (node with the minimum key).

public void deleteMin(){
  if(isEmpty())
   throw new NoSuchElementException("Empty tree!");
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = deleteMin(root);
  if(!isEmpty())
   root.color = Color.black;
 }
 private ColoredTreeNode deleteMin(ColoredTreeNode node){
  if(node.left == null)
   return null;
  if(!isRed(node.left) && !isRed(node.left.left))
   node = moveRedLeft(node);
  node.left = deleteMin(node.left);
  return balance(node);
 }

2. Delete the right most leaf(node with the maximum key)

public void deleteMax(){
  if(isEmpty())
   throw new NoSuchElementException("Empty tree!");
  //delete a red node
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = deleteMax(root);
  if(!isEmpty()) 
   root.color = Color.black;
 }
 private ColoredTreeNode deleteMax(ColoredTreeNode node){
  //note the root is red from the above method
  if(isRed(node.left))
   root = rotateRight(node);
  //BST, max is always at right
  if(node.right == null)
   return null;
  if(!isRed(node.right) && !isRed(node.right.left))
   node = moveRedRight(node);
  node.right = deleteMax(node.right);
  return balance(node);
 }

3. Delete a node given a key

This follows the traditional BST deletion rule. Find the node, replace it with the node with the smallest key in the right subtree (or node with the largest key in the left subtree) and then recursively delete the replaced node. The recursion will follow either deleting the min (the left most leaf) or the max(deleting the right most leaf)'s rule. 

public void delete(Comparable key){
  if(!contains(key)){
   System.err.println("Symbol table does not contain " + key);
   return;
  }
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = delete(root, key);
  if(!isEmpty())
   root.color = Color.black;
  //assert check();
 }
 private ColoredTreeNode delete(ColoredTreeNode node, Comparable key){
  if(key.compareTo((T)node.key) < 0){
   if(!isRed(node.left) && !isRed(node.left.left))
    node = moveRedLeft(node);
   node.left = delete(node.left, key);
  }
  else {
   if(isRed(node.left))
    node = rotateRight(node);
   if(key.compareTo((T)node.key) == 0 && (node.right == null))
    return null;
   if(!isRed(node.right) && !isRed(node.right.left))
    node = moveRedRight(node);
   if(key.compareTo((T)node.key) == 0){
    //find minimum node in the right subtree
    ColoredTreeNode x = min(node.right);
    node.key = x.key;
    node.data = x.data;
    node.right = deleteMin(node.right);
   }
   else
    node.right = delete(node.right, key);
  }
  return balance(node); 
 }

The full source code (!)
I used the real "Color" in java.awt.Color class, which is not a very good idea. The color is represented using 3 1byte memory, one color will take 3 bytes. However, since we are only consider red and black in this case, a boolean variable red = true (or false), which only takes 1 bit, is enough. The source code can also be found on my Github.

package redBlackTree;

import java.awt.Color;
import java.util.*;

/**
 * This class implements a left leaning red-black tree
 * if there is an extra node, it will always be at the 
 * left side
 * @author shirleyyoung
 * @param 
 *
 * @param 
 */

public class RedBlackBST {
 private ColoredTreeNode root;
 
 /**
  * constructor
  */
 public RedBlackBST(){
  root = null;
  //System.out.println("New tree constructed!");
 }
 
 /************************************************
  * Search
  ************************************************/
 public boolean contains(Comparable k) {
  return get(k) != null;
 }
 public Object get(Comparable key){
  return get(root, key);
 }
 private Object get(ColoredTreeNode node, Comparable k){
  while(node != null){
   int cmp = node.key.compareTo((T)k);
   if(cmp > 0) node = node.left;
   else if(cmp < 0) node = node.right;
   else return node.data;
  }
  return null;
 }
 /*************************************************
  * insertion
  *************************************************/
 public void insert(Comparable k, Object obj){
  root = insert(k, obj, root);
  //System.out.println(root.key);
  root.color = Color.black;
  assert check();
 }
 private ColoredTreeNode insert(Comparable k, Object obj, ColoredTreeNode root){
  if(root == null){
   //System.out.println("Inserted new node!");
   return new ColoredTreeNode(k, obj, Color.red, 1);
  }
  int cmp = k.compareTo((T)root.key);
  if(cmp < 0)
   root.left = insert(k, obj, root.left);
  else if (cmp > 0)
   root.right = insert(k, obj, root.right);
  else
   root.data = obj;
  /*
   * rotate and re-adjust color
   */
  //the new added node is the right child 
  //of the root, since the tree is left leaning
  //we need to left rotate the tree
  if(isRed(root.right) && !isRed(root.left))
   root = rotateLeft(root);
  //two consecutive red nodes, rotate right
  if(isRed(root.left) && isRed(root.left.left))
   root = rotateRight(root);
  //a red node must have two black children
  //flip the color if a node have two red children
  //if the parent is black, and the parent's parent is 
  //red, flip the nodes will cause two red parents on the 
  //left, and the tree will rotate right to correct it
  if(isRed(root.left) && isRed(root.right))
   flipColors(root);
  root.numSubtree = size(root.left) + size(root.right) + 1;
  //System.out.println(root.key);
  return root; 
 }
 /*****************************************************
  * Deletion
  *****************************************************/
 /**
  * delete the node with minimum key
  */
 public void deleteMin(){
  if(isEmpty())
   throw new NoSuchElementException("Empty tree!");
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = deleteMin(root);
  if(!isEmpty())
   root.color = Color.black;
 }
 private ColoredTreeNode deleteMin(ColoredTreeNode node){
  if(node.left == null)
   return null;
  if(!isRed(node.left) && !isRed(node.left.left))
   node = moveRedLeft(node);
  node.left = deleteMin(node.left);
  return balance(node);
 }
 /**
  * delete the node with the maximum key
  */
 public void deleteMax(){
  if(isEmpty())
   throw new NoSuchElementException("Empty tree!");
  //delete a red node
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = deleteMax(root);
  if(!isEmpty()) 
   root.color = Color.black;
 }
 private ColoredTreeNode deleteMax(ColoredTreeNode node){
  //note the root is red from the above method
  if(isRed(node.left))
   root = rotateRight(node);
  //BST, max is always at right
  if(node.right == null)
   return null;
  if(!isRed(node.right) && !isRed(node.right.left))
   node = moveRedRight(node);
  node.right = deleteMax(node.right);
  return balance(node);
 }
 /**
  * delete a node given a key
  * @param key
  */
 public void delete(Comparable key){
  if(!contains(key)){
   System.err.println("Symbol table does not contain " + key);
   return;
  }
  if(!isRed(root.left) && !isRed(root.right))
   root.color = Color.red;
  root = delete(root, key);
  if(!isEmpty())
   root.color = Color.black;
  assert check();
 }
 private ColoredTreeNode delete(ColoredTreeNode node, Comparable key){
  if(key.compareTo((T)node.key) < 0){
   if(!isRed(node.left) && !isRed(node.left.left))
    node = moveRedLeft(node);
   node.left = delete(node.left, key);
  }
  else {
   if(isRed(node.left))
    node = rotateRight(node);
   if(key.compareTo((T)node.key) == 0 && (node.right == null))
    return null;
   if(!isRed(node.right) && !isRed(node.right.left))
    node = moveRedRight(node);
   if(key.compareTo((T)node.key) == 0){
    //find minimum node in the right subtree
    ColoredTreeNode x = min(node.right);
    node.key = x.key;
    node.data = x.data;
    node.right = deleteMin(node.right);
   }
   else
    node.right = delete(node.right, key);
  }
  return balance(node); 
 }
 /**********************************************
  * reconstruct methods
  **********************************************/
 
 private ColoredTreeNode rotateRight(ColoredTreeNode node){
  ColoredTreeNode x = node.left;
  node.left = x.right;
  x.right = node;
  x.color = x.right.color;
  x.right.color = Color.red;
  x.numSubtree = node.numSubtree;
  node.numSubtree = size(node.left) + size(node.right) + 1;
  return x;
 }
 
 private ColoredTreeNode rotateLeft(ColoredTreeNode node){
  ColoredTreeNode x = node.right;
  node.right = x.left;
  x.left = node;
  x.color = x.left.color;
  x.left.color = Color.red;
  x.numSubtree = node.numSubtree;
  node.numSubtree = size(node.left) + size(node.right) + 1;
  return x;
 }
 /**
  * flip the color of the node and its children
  * @param node
  */
 private void flipColors(ColoredTreeNode node){
  node.color = node.color == Color.red ? Color.black : Color.red;
  node.left.color = node.left.color == Color.red ? Color.black : Color.red;
  node.right.color = node.right.color == Color.red ? Color.black : Color.red; 
 }
 /**
  * Assuming that node is red and both node.left and node.left.left
  * are black, make node.left or one of its children red
  * @param node
  * @return
  */
 private ColoredTreeNode moveRedLeft(ColoredTreeNode node){
  flipColors(node);
  if(isRed(node.right.left)){
   node.right = rotateRight(node.right);
   node = rotateLeft(node);
   flipColors(node);
  }
  return node;
 }
 /**
  * Assuming node is red and both node.right and node.right.left
  * are black, make node.right or one of its children red
  * @param node
  * @return
  */
 private ColoredTreeNode moveRedRight(ColoredTreeNode node){
  flipColors(node);
  if(isRed(node.left.left)){
   node = rotateRight(node);
   flipColors(node);
  }
  return node;
 }
 private ColoredTreeNode balance(ColoredTreeNode node){
  if(isRed(node.right))
   node = rotateLeft(node);
  if(isRed(node.left) && isRed(node.left.left))
   node = rotateRight(node);
  if(isRed(node.left) && isRed(node.right))
   flipColors(node);
  node.numSubtree = size(node.left) + size(node.right) + 1;
  return node;
 }
 /***************************************************
  * Other helper and utility methods
  ***************************************************/
 /**
  * check if a tree node is red,
  * if not, it is black
  * @param node
  * @return
  */
 private boolean isRed(ColoredTreeNode node){
  if(node == null)
   return false;
  return node.color == Color.red;
 }
 /**
  * return number of nodes in the tree
  * @return
  */
 public int size(){
  return size(root);
 }
 /**
  * return number of nodes in the subtree rooted at node
  * @param node
  * @return
  */
 private int size(ColoredTreeNode node){
  if(node == null)
   return 0;
  return node.numSubtree;
 }
 
 /**
  * find the node with the smallest key in subtree rooted at node
  * @param node
  * @return
  */
 public Comparable min(){
  if(isEmpty())
   return null;
  return min(root).key;
 }
 private ColoredTreeNode min(ColoredTreeNode node){
  if(node.left == null)
   return node;
  return min(node.left);
 }
 /**
  * find the node with the largest key in subtree rooted at node
  * @param node
  * @return
  */
 public Comparable max(){
  if(isEmpty())
   return null;
  return max(root).key;
 }
 private ColoredTreeNode max(ColoredTreeNode node){
  if(node.right == null)
   return node;
  return max(node.right);
 }
 
 /**
  * if it is an empty tree
  * @return
  */
 public boolean isEmpty(){
  return root == null;
 }
 
 /*******************************************************
  * check integrity of the tree
  *******************************************************/
 private boolean check(){
  if(!isBST()) 
   System.out.println("Not a BST!");
  if(!isSizeConsistent())
   System.out.println("Subtree counts not consistent!");
  if(!isBalanced())
   System.out.println("Not balanced tree!");
  return isBST() && isSizeConsistent() && isBalanced();
 }
 private boolean isSizeConsistent(){
  return isSizeConsistent(root);
 }
 private boolean isSizeConsistent(ColoredTreeNode root){
  if(root == null)
   return true;
  if(root.numSubtree != size(root.left) + size(root.right) + 1)
   return false;
  return isSizeConsistent(root.left) && isSizeConsistent(root.right);
 }
 private boolean isBST(){
  return isBST(root, null, null);
 }
 private boolean isBST(ColoredTreeNode node, Comparable min, Comparable max){
  if(node == null) return true;
  if(min != null && node.key.compareTo((T)min) <= 0) return false;
  if(max != null && node.key.compareTo((T)max) >= 0) return false;
  return isBST(node.left, min, node.key) && isBST(node.right, node.key, max);
 }
 /**
  * check if every root to leaf path have the same number
  * of black nodes
  * @return
  */
 public boolean isBalanced(){
  int blackNodes = 0;
  ColoredTreeNode node = root;
  while(node != null){
   if(!isRed(node))
    blackNodes++;
   node = node.left;
  }
  return isBalanced(root, blackNodes);
 }
 private boolean isBalanced(ColoredTreeNode node, int blackNodes){
  if(node == null) return blackNodes == 0;
  if(!isRed(node)) blackNodes--;
  return isBalanced(node.left, blackNodes) && isBalanced(node.right, blackNodes);
 }
 /**
  * output for check
  */
 public void printTree ()
 {
  if (root == null)
   return;
  Queue> queue = new LinkedList> ();
  queue.offer(root);
  //System.out.println(queue.peek().key);
  while (!queue.isEmpty())
  {
   int size = queue.size();
   for (int i = 0; i < size; i++)
   {
    ColoredTreeNode head = queue.poll();
    System.out.print(head.key + " ");
    if(head.left != null)
     queue.offer(head.left);
    if(head.right != null)
     queue.offer(head.right);
   }
   System.out.println("");

  }
 }
}
public class ColoredTreeNode {
 Comparable key;
 Object data; 
 Color color;
 ColoredTreeNode left;
 ColoredTreeNode right;
 int numSubtree; //subtree count
 public ColoredTreeNode(Comparable key, Object data, Color c, int N){
  this.key = key;
  this.data = data;
  left = null;
  right = null;
  color = c;
  numSubtree = N;
 }

}

Some notes about AVL tree
In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if any time they differ by more than one, rebalancing is done to restore the property. Look up, insertion and deletion all take O(logn) time. For lookup-intensive applications, AVL trees are faster than red-black trees because they are more rigidly balances.

Insertion
Every time a new node is inserted, it is necessary to check each of the node's ancestors for consistency with the rules of AVL. The balance factor is calculated as:

balanceFactor = height(left subtree) - height(right subtree)

Since with a single insertion the height of an AVL subtree cannot increase by more than one, the temporary balance factor of a node will be in the range from -2 to 2. For each node checked, if the balance factor remains in the range from -1 to 1, then only corrections of the balance factor, but no rotations are necessary. However, if the balance factor becomes less than -1 or greater than 1, the subtree rooted at this is unbalanced.

Deletion follows BST deletion rule, but needs to check balance factor each time.

Number of nodes between two nodes

given two nodes of a binary tree, find number of nodes on the path between the two nodes.

      1
     2  3
   4      5
     
   4, 3 -> (4-2-1-3): 4

Update 2015 - 04 - 05:
Thanks for the comment, I realized that this can be done using in order traversal in one pass. And the code is much simpler.

public int numberOfNodes2(TreeNode root, TreeNode n1, TreeNode n2){
  return inOrder(root, n1, n2, false, false, 0);
 }
 private int inOrder(TreeNode root, TreeNode n1, TreeNode n2, boolean first, boolean second, int sum){
  if(root == null|| second == true)
   return 0;
  sum = inOrder(root.left, n1, n2, first, second, sum);
  if(root == n1)
   first = true;
  if(root == n2)
   second = true;
  if(first == true && second == false)
   sum++;
  sum = inOrder(root.right, n1, n2, first, second, sum);
  return sum;
 }

I use a common ancestor approach. Find the common ancestor first, then find number of nodes from the ancestor to one node and the other one. The nodes between those two nodes are the sum of two paths minus the double count of the ancestor.

Right now my code needs to go through the tree twice: find the ancestor and get the depth. I am looking for a way to reduce it to one pass...

public class NumberOfNodesOnPath {
 public static int numberNodes(TreeNode root, TreeNode n1, TreeNode n2){
  if(n1 == null || n2 == null)
   throw new NullPointerException("Null tree node!");
  if(n1 == n2)
   return 1;
  TreeNode commonAncestor = getAncestor(root, n1, n2);
  return getDepth(commonAncestor, n1) + getDepth(commonAncestor, n2) - 1;
 }
 private static int getDepth(TreeNode root, TreeNode n){
  if(root == null)
   return Integer.MAX_VALUE / 2;
  if(root == n)
   return 1;
  if(root.left == n || root.right == n)
   return 2;
  return Math.min(getDepth(root.left, n), getDepth(root.right,n)) + 1;
 }
 private static TreeNode getAncestor(TreeNode root, TreeNode n1, TreeNode n2){
  if(root == null || n1 == null || n2 == null)
   return null;
  if(isChild(root.left, n1) && isChild(root.left, n2))
   return getAncestor(root.left, n1, n2);
  if(isChild(root.right, n1) && isChild(root.right, n2))
   return getAncestor(root.right, n1, n2);
  return root;
 }
 private static boolean isChild(TreeNode root, TreeNode n){
  if(root == null)
   return false;
  if(root == n)
   return true;
  return isChild(root.left, n) || isChild(root.right, n);
 }

 public static void main(String[] args) {
  TreeNode n1 = new TreeNode(1);
  TreeNode n2 = new TreeNode(2);
  TreeNode n3 = new TreeNode(3);
  TreeNode n4 = new TreeNode(4);
  TreeNode n5 = new TreeNode(5);
  TreeNode n6 = new TreeNode(6);
  n1.left = n2;
  n1.right = n3;
  n2.left = n4;
  n2.right = n6;
  n3.right = n5;
  System.out.println(numberNodes(n1, n4, n4));

 }

}

Find number of online users given a list of user's login and logout time

A period of time where users login and logout, given a sets of login and logout

time pairs, write a function that can show the number of users online at any given time

Using interval tree  to solve the problem.

public class findNumberOfUsers {
 private static class LogTime implements Comparable{
  int start;
  int end;
  LogTime(int start, int end) {
   if (end < start)
    throw new IllegalArgumentException("Illegal input time interval");
   this.start = start;
   this.end = end;
  }
  public boolean contains(int time) {
   return start <= time && end >= time;
  }
  public int compareTo(LogTime timeInterval) {
   if (start < timeInterval.start)
    return -1;
   else if (start > timeInterval.start)
    return 1;
   else if (end < timeInterval.end)
    return -1;
   else if (end > timeInterval.end)
    return 1;
   else
    return 0;
  }
  public String toString() {
   return "[" + String.valueOf(start) + ", " + String.valueOf(end) + "]";
  }
 }
 
 private class Node {
  LogTime timeInt;
  V label;
  Node left, right;
  //int N;
  int max;
  Node (LogTime time, V label) {
   timeInt = time;
   this.label = label;
   this.max = time.end;
  } 
 }
 private Node root;
 
 /************************
  * find a LogTime
  ***********************/
 public boolean contains(LogTime time) {
  return get(time) != null;
 }
 public V get(LogTime time) {
  return get(root, time);
 }
 private V get(Node node, LogTime time) {
  if (node == null)
   return null;
  int cmp = time.compareTo(node.timeInt);
  if (cmp == 0)
   return node.label;
  else if (cmp < 0) {
   return get(node.left, time);
  }
  else {
   return get(node.right, time);
  }
 }
 
 /************************
  * insertion
  ***********************/
 public void put(LogTime time, V label) {
  if (contains(time)) {
   System.out.println("Node exists!");
   return;
  }
  root = insert(root, time, label);
 }
 private Node insert(Node node, LogTime time, V label) {
  if (node == null) {
   return new Node(time, label);
  }
  int cmp = time.compareTo(node.timeInt);
  if (cmp < 0) 
    node.left = insert(node.left, time, label);
  else 
   node.right = insert(node.right, time, label);
  fix(node);
  return node;
 }
 private void fix(Node node) {
  if (node == null)
   return;
  node.max = max3(node.timeInt.end, max(node.left), max(node.right));
 }
 private int max(Node node) {
  if (node == null)
   return Integer.MIN_VALUE;
  return node.max;
 }
 private int max3(int a, int b, int c) {
  return Math.max(a, Math.max(b, c));
 }
 
 /**
  * given a time t, return number of users online
  * @param t
  * @return
  */
 
 public int search(int t) {
  return search(root, t);
 }
 
 private int search(Node node, int t) {
  if (node == null)
   return 0;
  int left = 0;
  int right = 0;
  int ro = 0;
  if (node.timeInt.contains(t))
   ro = 1;
  if (node.left != null && t < node.left.max)
   left = search(node.left, t);
  if (node.right != null && t  fu = new findNumberOfUsers ();
  for (int i = 0; i < N; i++) {
   int start = (int) (Math.random() * 100);
   int end = (int)(Math.random() * 50) + start;
   LogTime time = new LogTime(start, end);
   System.out.println(time.toString());
   fu.put(time, String.valueOf(i));
  }
  
  System.out.println(fu.search(79));
  
 }

}

Interval Search Tree

Consider we have a situation where we have a list of intervals and we need the following operations:

1. Add an interval;
2. Remove an interval;
3. Given an interval, search if it overlaps with any intervals in the list and return all those intervals.

Yup, the answer is the title; interval search tree.

The interval search tree follows a binary search tree structure. Each node of the tree stores the following information:

1. interval: the interval;
2. label: a unique label;
3. max: the high value of all intervals in the subtree of the current node is smaller than this one.

The compare method of the interval follows to following rule:

1. The interval with the lower low value is always smaller

2. If the low is the same, the interval with the lower high is smaller

Insertion: insert the interval based on the BST rule, i.e., recursively find the right position and insert at that position. 

However, if we want to insert a new interval and make it as the new root, a swap node operation is needed. Note this operation may make the tree unbalanced. 

Find the correct position and insert

Right rotate 

Left rotate

Deletion: Still follows the BST recursion rules. When the interval is found and both left and right child exist, join two children and their subtrees. Either child can be selected as the new root, yet the one with larger subtree sizes is preferred. 

Search: Follows the BST recursion rules. If root intersects with the interval, return root (add root to the list), recursively search the left subtree and right subtree. 

package intervalSearchTree;
import java.util.*;
public class IntervalSearchTree {
 /**
  * tree node class
  *
  */
 private class Node {
  Interval interval;
  V label;
  Node left, right;
  int N;//size of subtree (number of nodes) rooted at this node
  int max;
  Node (Interval interval, V label) {
   this.interval = interval;
   this.label = label;
   this.N = 1;
   this.max = (int) interval.high;
  }
 }
 private Node root;
 
 /***************************************
  * search if an interval is in the tree
  * @param interval
  * @return
  ***************************************/
 public boolean contains(Interval interval) {
  return get(interval) != null;
 }
 public V get(Interval interval) {
  return get(root, interval);
 }
 private V get(Node node, Interval interval) {
  if (node == null)
   return null;
  int cmp = interval.compareTo(node.interval);
  if (cmp < 0)
   return get(node.left, interval);
  else if (cmp > 0)
   return get(node.right, interval);
  else
   return node.label;
 }
 
 
 /*****************************
  * insertion 
  *****************************/
 public void put(Interval interval, V label) {
  if (contains(interval)) {
   System.out.println("Duplicate interval!");
   return;
  }
  root = insert(root, interval, label);
 } 
 /**
  * insert a node based on BST rule
  * @param node
  * @param interval
  * @param label
  * @return
  */
 private Node insert(Node node, Interval interval, V label) {
  if (node == null)
   return new Node(interval, label);
  int cmp = interval.compareTo(node.interval);
  if (cmp < 0) {
   node.left = insert(node.left, interval, label);
  }
  else {
   node.right = insert(node.right, interval, label);
  }
  fix(node);
  return node;
 }
 /**
  * insert the new interval as the root of the tree
  * @param interval
  * @param label
  */
 public void insertRoot(Interval interval, V label) {
  if (contains(interval)) {
   System.out.println("Duplicate interval!");
   return;
  }
  root = insertRoot(root, interval, label); 
 }
 /**
  * insert the node at the correct position
  * rotate the node so that the new node will be the root 
  * while still maintaining the BST structure
  * @param node
  * @param interval
  * @param label
  * @return
  */
 private Node insertRoot(Node node, Interval interval, V label) {
  if (node == null)
   return new Node (interval, label);
  int cmp = interval.compareTo(node.interval);
  if (cmp < 0) {
   node.left = insertRoot(node.left, interval, label);
   node = rotR(node);
  }
  else {
   node.right = insertRoot(node.right, interval, label);
   node = rotL(node);
  }
  return node;
 }
 
 /***************************************
  * deletion
  * *************************************/
 public V remove(Interval interval) {
  V value = get(interval);
  root = remove(root, interval);
  return value;
 }
 private Node remove(Node node, Interval interval) {
  if (node == null)
   return null;
  int cmp = interval.compareTo(node.interval);
  if (cmp < 0)
   node.left = remove(node.left, interval);
  else if (cmp > 0)
   node.right = remove(node.right, interval);
  else
   node = join(node.left, node.right);
  fix(node);
  return node;
 }
 /**
  * join the left and right subtree of a node 
  * once the node is deleted
  * use a random number to determine whether the new node is the left child
  * or the right child
  * @param a
  * @param b
  * @return
  */
 private Node join(Node a, Node b) {
  if (a == null)
   return b;
  if (b == null)
   return a;
  //generate a number between 0.0 to 1.0
  if (Math.random() * (double)(size(a) + size(b)) < (double)size(a)) {
   a.right = join(a.right, b);
   fix(a);
   return a;
  }
  else {
   b.left = join(a, b.left);
   fix(b);
   return b;
  }
 }
 
 
 
 /******************************
  * Search the Interval tree
  ******************************/
 public Interval search(Interval interval) {
  return search(root, interval);
 }
 public Interval search(Node node, Interval interval) {
  while (node != null) {
   if (interval.intersects(node.interval))
    return node.interval;
   else if (node.left == null)
    node = node.right;
   else if (node.left.max < interval.low)
    node = node.right;
   else
    node = node.left;
  }
  return null;
 }
 /**
  * return all intervals that intersect the given interval
  * running time is proportional to RlogN, where R 
  * is the number of intersections
  * @param interval
  * @return
  */
 public Iterable searchAll (Interval interval) {
  LinkedList list = new LinkedList ();
  searchAll(root, interval, list);
  return list;
 }
 public boolean searchAll(Node node, Interval interval, LinkedList list) {
  boolean found_root = false;
  boolean found_left = false;
  boolean found_right = false;
  if (node == null)
   return false;
  if (interval.intersects(node.interval)) {
   list.add(node.interval);
   found_root = true;
  }
  if (node.left != null && node.left.max >= interval.low)
   found_left = searchAll(node.left, interval, list);
  if (node.right != null && node.right.max >= interval.high)
   found_right = searchAll(node.right, interval, list);
  return found_root || found_left || found_right;
 }
 
 
 
 /**********************************
  * useful methods
  **********************************/
 public int size() {
  return size(root);
 }
 private int size(Node node) {
  if (node == null)
   return 0;
  else
   return node.N;
 }
 public int height() {
  return height(root);
 }
 private int height(Node node) {
  if (node == null)
   return 0;
  return 1 + Math.max(height(node.left), height(node.right));
 }
 /**
  * fix auxilliar information 
  * subtree count and max fields
  * @param node
  */
 private void fix(Node node) {
  if (node == null)
   return;
  node.N = 1 + size(node.left) + size(node.right);
  node.max = max3(node.interval.high, max(node.left), max(node.right));
 }
 private int max(Node node) {
  if (node == null)
   return Integer.MIN_VALUE;
  return node.max;
 }
 
 private int max3(int a, int b, int c) {
  return Math.max(a, Math.max(b, c));
 }
 /**
  * right rotate
  *     1             2
  *    / \           / \
  *   2   3    ->   4   1
  *  / \               / \
  * 4   5             5   3
  * @param h
  * @return
  */
 private Node rotR(Node h) {
  Node l = h.left;
  h.left = l.right;
  l.right = h;
  fix(h);
  fix(l);
  return l;
 }
 /**
  * left rotate
  *     1             3
  *    / \           / \
  *   2   3    ->   1   5
  *      / \       / \
  *     4   5     2   4
  *     
  * @param h
  * @return
  */
 private Node rotL(Node h) {
  Node r = h.right;
  h.right = r.left;
  r.left = h;
  fix(h);
  fix(r);
  return r;
 }
 /********************************
  * Debugging 
  ********************************/
 public boolean check() {
  return checkCount() && checkMax();
 }
 
 private boolean checkCount() {
  return checkCount(root);
 }
 private boolean checkCount(Node node) {
  if (node == null)
   return true;
  return checkCount(node.left) && checkCount(node.right) 
    && (node.N == 1 + size(node.left) + size(node.right));
 }
 private boolean checkMax() {
  return checkMax(root);
 }
 private boolean checkMax(Node node) {
  if (node == null)
   return true;
  return node.max == max3(node.interval.high, max(node.left), max(node.right));
 }
}
public class Interval implements Comparable{
 public final int low;
 public final int high;
 Interval(int low, int high) {
  if (high < low)
   throw new IllegalArgumentException("Illegal argument");
  this.low = low;
  this.high = high;
 }
 
 public boolean contains(int x) {
  return low <= x && high >= x;
 }
 public boolean intersects (Interval interval) {
  if(high < interval.low)
   return false;
  if (low > interval.high)
   return false;
  return true;
 }
 
 public int compareTo(Interval interval) {
  if (low < interval.low)
   return -1;
  else if (low > interval.low)
   return 1;
  else if (high < interval.high)
   return -1;
  else if (high > interval.high)
   return 1;
  else
   return 0;
 }
 public String toString()
 {
  return  "[" + String.valueOf(low) + " ," + String.valueOf(high) + "]"; 
 }

}

src on Github: https://github.com/shirleyyoung0812/intervalSearchTree.git

Reverse a BST, find the kth largest element in BST

This is a FB interview question.
1. Reverse the BST;
2. find the kth largest element in O(n) time;
3. find the kth largest element in O(log n) time.

The first one is easy, recursively flip the left and right child of the tree.
The second one too, use in order traversal.
Now comes the third one. Here is an answer I found.

Here's just an outline of the idea:

Let each node in the BST have a field that returns the number of elements in its left and right subtree. Let the left subtree of node T contain only elements smaller than T and the right subtree only elements larger than or equal to T.

Now, suppose we are at node T:

1. k == num_elements(left subtree of T), then the answer we're looking for is the value in nodeT
2. k > num_elements(left subtree of T) then obviously we can ignore the left subtree, because those elements will also be smaller than the kth smallest. So, we reduce the problem to finding the k - num_elements(left subtree of T) smallest element of the right subtree.
3. k < num_elements(left subtree of T), then the kth smallest is somewhere in the left subtree, so we reduce the problem to finding the kth smallest element in the left subtree.

This is O(log N) on average (assuming a balanced tree).

But the problem is, how to get the size of the tree? In the end, I wrote a Tree class. However, there is a bug in this class: I can only build the tree bottom up: otherwise the children of the subtree will not be added into the parent's children list.

import java.util.*;
public class Tree {
 private int size;
 TreeNode node;
 Tree left;
 Tree right;
 List children;
 public Tree() {
  children = new ArrayList();
  size = 0;
 }
 public Tree(int rootVal) {
  node = new TreeNode(rootVal);
  children = new ArrayList ();
  left = new Tree();
  right = new Tree();
  size++;
 }
 private void addChildren(Tree tree) {
  children.addAll(tree.children);
  size += tree.children.size();
 }
 public void buildLeft(Tree leftTree) {
  node.left = leftTree.node;
  left = leftTree;
  children.add(leftTree.node);
  size++;
  addChildren(leftTree);
 }
 
 public void buildRight(Tree rightTree) {
  node.right = rightTree.node;
  right = rightTree;
  children.add(rightTree.node);
  size++;
  children.addAll(rightTree.children);
  size += rightTree.children.size();
 }
 public int size() {
  return size;
 }

}
public class TreeNode {

  int val;
  TreeNode left;
  TreeNode right;
  //TreeNode parent;
  TreeNode(int x) { val = x;}

}

Here are the methods for the three problems:

public static void reverseBST (TreeNode root) {
  if (root == null || (root.left == null && root.right == null))
   return;
  TreeNode tmp = root.left;
  root.left = root.right;
  root.right = tmp;
  reverseBST(root.right);
  reverseBST(root.left);
 }
 static int count = 0;
 /**
  * O(n) complexity
  * @param root
  * @param k
  * @return
  */
 public static int kthLargest(Tree root, int k) {
  if (root == null)
   return -1;
  return findKth(root.node, k).val;
  
 }
 private static TreeNode findKth (TreeNode root, int k) {
  if (root == null)
   return root;
  TreeNode right = findKth(root.right, k);
  if (count == k)
   return right;
  ++count;
  if (count == k)
   return root;
  return findKth(root.left, k);
 }
 /**
  * O(log n) complexity
  * @param root
  * @param k
  * @return
  */
    public static TreeNode findKth(Tree root, int k) {
     if (root.right.size() == k - 1)
      return root.node;
     else if (root.right.size() < k - 1)
      return findKth(root.left, k - root.right.size() - 1);
     else
      return findKth(root.right, k);
  
 }

Isomorphic Trees

An easier version of Scramble String. Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e., by swapping left and right children of a number of nodes. Two empty trees are isomorphic.

Image source: http://www.geeksforgeeks.org/tree-isomorphism-problem/

The above two trees are isomorphic because : 2 & 3, Null & 6, 7 & 8 are flipped.

public boolean isIsomorphic(TreeNode p, TreeNode q){
    if(p == null)
        return q == null;
    if(q == null)
        return false;
    if(p.val != q.val)
        return false;
    return (isIsomorphic(p.left, q.left) && isIsomorphic(p.right, q.right)) 
    || (isIsomorphic(p.left, q.right) && isIsomorphic(p.right, q.left));
}

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

confused what "{1,#,2,3}" means? 

Update, actually, just do in order traversal.

Consider this wrong BST:

       1
    /      \
  2        3

When we go down to the bottom, we know the left child should be smaller than root, which gives us the first wrong element, lastElement, 2. And now we have the firstElement, and the second element is then the root.


If there is a wrong element in a BST. It means the element must have a larger value compare to it's right child or a smaller value compare to it's left child.
When we traverse down to the left leaf, the last node we visited must have a larger value, assuming we have a correct tree, if it has a smaller value compare to the root, the last node is a wrong element. The same as we traverse up from the right leaf.
When we traverse down to the right leaf, the last node we visited must have a smaller value compare to the root,  if it has a larger value, the root must be a wrong element.

 public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
 
public class RecoverBST {
    TreeNode firstElement = null;
    TreeNode secondElement = null;
    TreeNode lastElement = new TreeNode(Integer.MIN_VALUE);
    public void recoverTree(TreeNode root) {
        if (root == null)
            return;
        traverse(root);
        swap(firstElement, secondElement);
        
    }
    private void traverse(TreeNode root)
    {
        if (root == null)
            return;
        traverse(root.left);
        if (firstElement == null && root.val < lastElement.val)
            firstElement = lastElement;
        if (firstElement != null && root.val < lastElement.val)
            secondElement = root;
        lastElement = root;
        traverse(root.right);
    }
    private void swap(TreeNode n1, TreeNode n2)
    {
        int tmp = n1.val;
        n1.val = n2.val;
        n2.val = tmp;
    }
}

Convert Sorted Array/ Linked List to BST

I once found a question about which one is better for implementation of BST, a linked list or an array. The answer is the array, because it's easier to find the middle element.

These two problems explain the reason very clearly.

Convert Sorted List to BST

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.

I use the typical tree traversal way to build the BST: find the middle, take it as the root. Recursively build the left subtree and the right subtree. The only problem is, our findMiddle method should not return middle element, but the element before the middle element, because the left tree is built from head to the element before the middle. Moreover, this findMiddle method needs more attention on only one element in the list case. An alternative way could be like this.

Update 2015 - 03 - 05:
In the end, finding the middle method is not really optimal, the code is too long and tedious. I decide to implement the method based on inorder traversal. Set a static ListNode curr that track the list node that is going to be set as the root of the tree(or a subtree). Recursively construct the left subtree, proceed curr node, and construct the right tree. Left tree has size / 2, root takes 1 node, so right tree has size of size - size / 2 - 1.

public class ListNode {
ListNode curr;
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)
            return null;
        curr = head;
        int size = getSize(head);
        return getBST(size);
    }
    private TreeNode getBST(int size){
        if(size <= 0)
            return null;
        TreeNode left = getBST(size / 2);
        TreeNode root = new TreeNode(curr.val);
        root.left = left;
        curr = curr.next;
        root.right = getBST(size - 1 -size / 2);
        return root;
    }
    private int getSize(ListNode head){
        int size = 0;
        while(head != null){
            head = head.next;
            size++;
        }
        return size;
    }
}

public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; next = null; }
  }
 


// Definition for binary tree
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
 
public class BuildBST {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null)
            return null;
        if (head.next == null)
            return new TreeNode(head.val);
        ListNode preMid = findMiddle(head);
        ListNode mid = preMid.next;
        TreeNode root = new TreeNode(mid.val);
        root.right = sortedListToBST(mid.next);
        preMid.next = null;
        root.left = sortedListToBST(head);
        return root;
        
    }
    private ListNode findMiddle(ListNode head)
    {
        ListNode slow = head;
        ListNode fast = head.next;
        ListNode prev = null;
        while (fast != null && fast.next != null)
        {
            fast = fast.next.next;
            prev = slow;
            slow = slow.next;
        }
        return prev == null ? slow : prev;
    }
}

Convert Sorted Array to BST

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
 
public class Solution {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null || num.length == 0)
            return null;
        return buildTree(0, num.length - 1, num);
    }
    private TreeNode buildTree(int start, int end, int[] num)
    {
        if (start > end)
            return null;
        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(num[mid]);
        root.left = buildTree(start, mid - 1, num);
        root.right = buildTree(mid + 1, end, num);
        return root;
    }
}

Flatten Binary Tree to Linked List

A very beautiful tree traversal problem. No doubt recursion will be the solution.
Track the last node visited, and make the current node as the right child of the last node. Recursively go down to the left, then go to the right.

  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
 
public class FlattenTree {
    private TreeNode lastNode = null;
    public void flatten(TreeNode root) {
        if (root == null)
            return;
        if (lastNode != null)
        {
            lastNode.left = null;
            lastNode.right = root;
        }
        lastNode = root;
        TreeNode right = root.right;
        flatten(root.left);
        flatten(right);
            
        
    }
}

Populating Next Right Pointers in Each Node I & II

Updating a solution using Queue, O(n) complexity. Actually, this solution works for both problem...

public class TreeNextPointer {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        Queue q = new LinkedList ();
        q.offer(root);
        while(!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeLinkNode curr = q.poll();
                if(!q.isEmpty() && (i < size - 1))
                    curr.next = q.peek();
                if (curr.left != null)
                    q.offer(curr.left);
                if (curr.right != null)
                    q.offer(curr.right);
            }
        }
    }
}

The first one:

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

Nothing but a tree-like linked list traversal.
Set parent = root and nextLevel = parent.left. Using two loops, the outer one goes down each level and the second one assign pointers.

public class TreeNextPointer {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        TreeLinkNode parent = root;
        TreeLinkNode nextLevel = root.left;
        while (parent != null && nextLevel != null)
        {
            TreeLinkNode curr = null;
            //same level
            while (parent != null)
            {
                if (curr == null)
                    curr = parent.left;
                else
                {
                    curr.next = parent.left;
                    curr = curr.next;
                }
                curr.next = parent.right;
                curr = curr.next;
                parent = parent.next;
            }
            parent = nextLevel;
            nextLevel = parent.left;
        }
        
    }
}

The second one:

What if the given tree could be any binary tree? Would your previous solution still work?

Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

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

Overall it's not hard. However, I had a problem on assigning the nextLevel at the right place.
I did it outside the inner loop at first. Consider a case like this:

  1
 /   \
7    9
     /  \
    1   7
     \     \
      8    10

If I assign the nextLevel outside the inner loop like this:

while (parent != null)
        {
            TreeLinkNode curr = null;
            nextLevel = (parent.left == null) ? parent.right : parent.left;
            while (parent != null)
            {

When it traverse to parent = 7, there will be no nextLevel. And thus 8 will not be assigned the next pointer.

So it should be done in this way:

while (parent != null)
        {
            TreeLinkNode curr = null;
            nextLevel = null;
            while (parent != null)
            {
                if (nextLevel == null)
                     nextLevel = (parent.left == null) ? parent.right : parent.left;

The code:

public class TreeNextPointer {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        TreeLinkNode parent = root;
        TreeLinkNode nextLevel = null;
        while (parent != null)
        {
            TreeLinkNode curr = null;
            nextLevel = null;
            while (parent != null)
            {
                if (nextLevel == null)
                     nextLevel = (parent.left == null) ? parent.right : parent.left;
                if (parent.left != null)
                {
                    if (curr == null)
                        curr = parent.left;
                    else
                    {
                        curr.next = parent.left;
                        curr = curr.next;
                    }
                }
                if (parent.right != null)
                {
                    if (curr == null)
                        curr = parent.right;
                    else
                    {
                        curr.next = parent.right;
                        curr = curr.next;
                    }
                }
                parent = parent.next;
            }
            parent = nextLevel;
        }
        
    }
}