Tuesday, September 30, 2014

Nine Chapter: Lesson 3: Binary Tree


Outline:
1. Binary Tree DFS Traversal
  -- DFS traverse
        -- recursion
        -- stack
  -- Divide and Conquer
        -- quick sort
        -- merge sort
        -- most of the binary tree problems can be solved by D&Q

2. Binary Tree BFS Traversal
    -- Queue

3. Binary Search Tree
Binary tree DFS and D&Q templates:
/**
 * Copyright: NineChapter
 * - Algorithm Course, Mock Interview, Interview Questions
 * - More details on: http://www.ninechapter.com/
 */

Template 1: Traverse

public class Solution {
    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // do something with root
        traverse(root.left);
        // do something with root
        traverse(root.right);
        // do something with root
    }
}


Tempate 2: Divide & Conquer

public class Solution {
    public ResultType traversal(TreeNode root) {
        // null or leaf
        if (root == null) {
            // do something and return;
        }
        
        // Divide
        ResultType left = traversal(root.left);
        ResultType right = traversal(root.right);
        
        // Conquer
        ResultType result = Merge from left and right.
        return result;
    }
}


Questions can be solved by D & Q:

1. Binary Tree Pre-order Traversal:
http://buttercola.blogspot.com/2014/08/leetcode-binary-tree-preorder-traversal.html

Code (Java):
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;<pre class="brush:java">
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        
        if (root == null) {
            return result;
        }
        
        // Divide 
        List<Integer> left = preorderTraversal(root.left);
        List<Integer> right = preorderTraversal(root.right);
        
        result.add(root.val);
        result.addAll(left);
        result.addAll(right);
        
        return result;
    }
}

2. Maximum Depth of the binary tree:
http://buttercola.blogspot.com/2014/08/leetcode-maximum-depth-of-binary-tree.html
/
/**
 * Copyright: NineChapter
 * - Algorithm Course, Mock Interview, Interview Questions
 * - More details on: http://www.ninechapter.com/
 */

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return Math.max(left, right) + 1;
    }
}



3. Balanced binary tree
Given a binary tree, determine if it is height-balanced.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        return isBalancedHelper(root) != -1;
    }
    
    private int isBalancedHelper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = isBalancedHelper(root.left);
        int right = isBalancedHelper(root.right);
        
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        
        return Math.max(left, right) + 1;
    }
}

4. Minimum depth of the binary tree:


/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        return minDepthHelper(root);
    }
    
    private int minDepthHelper(TreeNode root) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        
        if(root.left == null && root.right == null) {
            return 1;
        }
        
        int left = minDepthHelper(root.left);
        int right = minDepthHelper(root.right);
        
        return Math.min(left, right) + 1;
    }
}


Note that the definition of the minimum depth of the binary tree.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. For e.g. 

                 1
                /
              2
             /
           3
The minimum depth of the tree is 3, not 1. That is why if root == null, its minimum depth is Integer.MAX_VALUE, meaning it is not passable.

5. Binary Tree Maximum Path Sum
http://buttercola.blogspot.com/2014/08/leetcode-binary-tree-maximum-path-sum.html
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int maxSum = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        maxPathSumHelper(root);
        return maxSum;
    }
    
    private int maxPathSumHelper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = maxPathSumHelper(root.left);
        int right = maxPathSumHelper(root.right);
        
        int arch = left + right + root.val;
        
        int pathSum = Math.max(root.val, Math.max(left, right) + root.val);
        
        maxSum = Math.max(maxSum, Math.max(arch, pathSum));
        
        return pathSum;
    }
}

BFS Template:
/**
 * Copyright: NineChapter
 * - Algorithm Course, Mock Interview, Interview Questions
 * - More details on: http://www.ninechapter.com/
 */

public class Solution {
    public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        ArrayList result = new ArrayList();
        
        if (root == null)
            return result;
            
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode head = queue.poll();
                level.add(head.val);
                if (head.left != null)
                    queue.offer(head.left);
                if (head.right != null)
                    queue.offer(head.right);
            }
            result.add(level);
        }
        
        return result;
    }
}


Questions can be solved by using BFS:
1. Binary tree level-order traversal:
http://buttercola.blogspot.com/2014/08/leetcode-binary-tree-level-order.html
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> levelList = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                TreeNode curr = queue.poll();
                levelList.add(curr.val);
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            result.add(levelList);
        }
        
        return result;
    }
}

2. Binary Tree ZigZag traversal
http://buttercola.blogspot.com/2014/08/leetcode-binary-tree-zigzag-level-order.html

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) {
            return result;
        }
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> levelList = new ArrayList<Integer>();
            if (result.size() % 2 == 0) {
                for (int i = 0; i < size; i++) {
                    TreeNode curr = queue.poll();
                    levelList.add(curr.val);
                    
                    if (curr.left != null) {
                        queue.offer(curr.left);
                    }
                    
                    if (curr.right != null) {
                        queue.offer(curr.right);
                    }
                }
            } else {
                Stack<Integer> stack = new Stack<Integer>();
                for (int i = 0; i < size; i++) {
                    TreeNode curr = queue.poll();
                    stack.push(curr.val);
                    
                    if (curr.left != null) {
                        queue.offer(curr.left);
                    }
                    
                    if (curr.right != null) {
                        queue.offer(curr.right);
                    }
                }
                
                while(!stack.isEmpty()) {
                    levelList.add(stack.pop());
                }
            }
            result.add(levelList);
        }
        
        return result;
    }
}

Binary Search Tree:
1. Validate Binary Search Tree
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private int lastVal = Integer.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        
        if (!isValidBST(root.left)) {
            return false;
        }
        
        if (root.val > lastVal) {
            lastVal = root.val;
        } else {
            return false;
        }
        
        if (!isValidBST(root.right)) {
            return false;
        }
        
        return true;
    }
}

2. Insert a node in BST
Reference: http://algs4.cs.princeton.edu/32bst/BST.java.html
   /***********************************************************************
    *  Insert key-value pair into BST
    *  If key already exists, update with new value
    ***********************************************************************/
    public void put(Key key, Value val) {
        if (val == null) { delete(key); return; }
        root = put(root, key, val);
        assert check();
    }

    private Node put(Node x, Key key, Value val) {
        if (x == null) return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        if      (cmp < 0) x.left  = put(x.left,  key, val);
        else if (cmp > 0) x.right = put(x.right, key, val);
        else              x.val   = val;
        return x;
    }


3. Search Range in a BST
Link: http://www.geeksforgeeks.org/print-bst-keys-in-the-given-range/

Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Print all the keys in increasing order.

Idea: Pruned inorder traversal

Code (Java):
import java.util.*;

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

public class Solution {
  public List<Integer> searchForRange(TreeNode root, int k1, int k2) {
    List<Integer> result = new ArrayList<Integer>();

    searchForRangeHelper(root, k1, k2, result);

    return result;
  }

  private void searchForRangeHelper(TreeNode root, int k1, int k2, List<Integer> result) {
    if (root == null) {
      return;
    }

    if (root.val > k1) {
      searchForRangeHelper(root.left, k1, k2, result);
    }

    if (root.val >= k1 && root.val <= k2) {
      result.add(root.val);
    }

    if (root.val < k2) {
      searchForRangeHelper(root.right, k1, k2, result);
    }
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    /// Construct a tree
    TreeNode root = new TreeNode(20);
    root.left = new TreeNode(12);
    root.right = new TreeNode(22);
    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(13);

    int k1 = 10;
    int k2 = 22;

    List<Integer> result = sol.searchForRange(root, k1, k2);
    
    /// Print out the result
    for (Integer elem : result) {
      System.out.println(elem);
    }
  }
}



4. Implement an iterator of a BST
Idea: in-order traversal. Note to use iteration instead of recursion. 



5. Delete a node in BST
http://algs4.cs.princeton.edu/32bst/
http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/BST-delete.html

Delete a node in BST is kind of complicated. It has three cases to consider:
1. The node to delete has no left and right children, i.e, it is a leaf node. Deletion this node is very simple, just delete is fine, i.e, if the node is a left child, let its parent.left = null. If node == parent.right, partent.right == null

2. The node to delete has only one subtree. This case is straight-forward as well. Delete this node and let its parent pointing to the children. 

3. The node to delete has two children. This case is the most complicated. But the basic idea is to find the maximum node in the left subtree, replace that node with the node to delete. Therefore, the replaced node is the maximum node in the left substree, and minimum in the right substree. So the tree is still a BST after deletion. 

Code (Java):
class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode (int x) { val = x; }
}

public class DeleteNode {
  public TreeNode deleteNode(TreeNode root, int val) {
    TreeNode dummyNode = new TreeNode(Integer.MIN_VALUE);
    dummyNode.left = root;

    findAndDelete(dummyNode, root, val);

    return dummyNode.left;
  }

  private void findAndDelete(TreeNode parent, TreeNode node, int target) {
    if (node == null) {
      return;
    }

    if (node.val == target) {
      deleteNode(parent, node);
    } else if (node.val > target) {
      findAndDelete(node, node.left, target);
    } else {
      findAndDelete(node, node.right, target);
    }
  }

  private void deleteNode(TreeNode parent, TreeNode node) {
    // Case 1: The deleted node is a leaf node
    if (node.left == null && node.right == null) {
      if (node == parent.left) {
        parent.left = null;
      } else {
        parent.right = null;
      }

      return;
    }

    // Case 2: The deleted node has only one child
    if (node.left == null) {
      if (node == parent.left) {
        parent.left = node.right;
      } else {
        parent.right = node.right;
      }
    } else {
      if (node == parent.left) {
        parent.left = node.left;
      } else {
        parent.right = node.left;
      }
    }
    
    // Case 3: The deleted node has two children
    if (node.left != null && node.right != null) {
      TreeNode maxNodeParent = node;
      TreeNode maxNodeLeft = node.left;

      while (maxNodeLeft.right != null) {
        maxNodeParent = maxNodeLeft;
        maxNodeLeft = maxNodeLeft.right;
      }

      // Delete the maxNodeLeft
      if (maxNodeLeft == maxNodeParent.left) {
        maxNodeParent.left = maxNodeLeft.left; /// Note that maxNodeLeft could have left children
      } else {
        maxNodeParent.right = maxNodeLeft.left;
      }

      // Replace that node with deleted node
      maxNodeLeft.left = node.left;
      maxNodeLeft.right = node.right;

      if (node == parent.left) {
        parent.left = maxNodeLeft;
      } else {
        parent.right = maxNodeLeft;
      }
    }
  }

  public void inOrderTraverse(TreeNode root) {
    if (root == null) {
      return;
    }

    inOrderTraverse(root.left);

    System.out.println(root.val);

    inOrderTraverse(root.right);
  }

  public static void main(String[] args) {
    DeleteNode sol = new DeleteNode();

    TreeNode root = new TreeNode(20);
    root.left = new TreeNode(12);
    root.right = new TreeNode(22);
    root.left.left = new TreeNode(10);

    root.right.left = new TreeNode(21);
    root.right.right = new TreeNode(26);

    root = sol.deleteNode(root, 26);

    sol.inOrderTraverse(root);
  }

}

Discussion:
Actually the code could be simplified. The case 1 and case 2 could be merged together because case 2 already covers the case 1. For the case 2, we don't need to handle node.right == null separately, because it is already covered in case 3. Note that the case 2 node.left == null must be checked separately because in case 3, maxNodeLeft = node.left, the while loop in case 3 will cause null pointer exception.
Code from Nine Chapter:
/**
 * Copyright: NineChapter
 * - Algorithm Course, Mock Interview, Interview Questions
 * - More details on: http://www.ninechapter.com/
 */
class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode (int x) { val = x; }
}

public class Solution {
    private void myDeleteNode(TreeNode parent, TreeNode node) {
        if (node.left == null) {
            if (parent.right == node) {
                parent.right = node.right;
            } else {
                parent.left = node.right;
            }
        } else {
            TreeNode maxNodeParent = node;
            TreeNode maxNode = node.left;
 
 // find the maximum node in the left sub tree
            while (maxNode.right != null) {
                maxNodeParent = maxNode;
                maxNode = maxNode.right;
            }

            if (maxNodeParent.left == maxNode) {
         maxNodeParent.left = maxNode.left;
            } else {
                maxNodeParent.right = maxNode.left;
            }

            // move replacedNode to node
            maxNode.left = node.left;
            maxNode.right = node.right;
            if (parent.left == node) {
                parent.left = maxNode;
            } else {
                parent.right = maxNode;
            }
        }
    }

    private void findAndDelete(TreeNode parent, TreeNode node, int val) {
        if (node == null) {
            return;
        }
        if (node.val == val) {
            myDeleteNode(parent, node);
        } else if (node.val < val) {
            findAndDelete(node, node.right, val);
        } else {
            findAndDelete(node, node.left, val);
        }
    }
    
    public TreeNode deleteNode(TreeNode root, int val) {
        TreeNode dummyNode = new TreeNode(0);
        dummyNode.left = root;
        findAndDelete(dummyNode, root, val);
        return dummyNode.left;
    }

    public void inOrderTraverse(TreeNode root) {
      if (root == null) {
        return;
      }

      inOrderTraverse(root.left);

      System.out.println(root.val);

      inOrderTraverse(root.right);
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      TreeNode root = new TreeNode(20);
      root.left = new TreeNode(12);
      root.right = new TreeNode(22);
      root.left.left = new TreeNode(10);

      root.right.left = new TreeNode(21);
      root.right.right = new TreeNode(26);

      root = sol.deleteNode(root, 29);

      sol.inOrderTraverse(root);
    }
}



6. Least(Lowest) Common Ancestor (LCA) in Binary Search Tree (BST)
LCA in BST is relatively easy to find out. There are basically three cases to consider:
1. both nod1.val and node2.val is less than the current root.val, the LCA must be in the left subtree.
2. Both node1 and node2 are greater than root, the LCA must be in the right subtree.
3. Else, node1 is less than root, node2 is greater than root, tis LCA must be the root itself.

Code(Java):
class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode (int x) { val = x; }
}

public class LCA {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
    if (root == null || node1 == null || node2 == null) {
      return root;
    }

    if (node1.val < root.val && node2.val < root.val) {
      return lowestCommonAncestor(root.left, node1, node2);
    } else if (node1.val > root.val && node2.val > root.val) {
      return lowestCommonAncestor(root.right, node1, node2);
    } else {
      return root;
    }
  }

  public static void main(String[] args) {
    LCA sol = new LCA();

    TreeNode root = new TreeNode(20);
    root.left = new TreeNode(8);
    root.right = new TreeNode(22);

    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(12);
    root.left.right.left = new TreeNode(10);
    root.left.right.right = new TreeNode(14);

    TreeNode ans = sol.lowestCommonAncestor(root, root.left.left, root.right);

    System.out.println(ans.val);
  }
}

Iterative Solution:
 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
    while (root != null) {
      if (node1.val < root.val && node2.val < root.val) {
        root = root.left;
      } else if (node1.val > root.val && node2.val > root.val) {
        root = root.right;
      } else {
        return root;
      }
    }
    return null;
  }
}


Discussion:
Time complexity is O(h), where h is the high of the BST.

7. LCA in Binary Tree
Note the difference between last question. Here the tree is just a binary tree, not BST. So the solution above does not work here since the tree does not have an order.

Naive Solution:
Find the path of node1 and node2, compare the elements of the path. When the first time they are different, return the element before it. 

Code (Java):
import java.util.*;

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

public class LCA {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
    List<TreeNode> path1 = new ArrayList<TreeNode>();
    List<TreeNode> path2 = new ArrayList<TreeNode>();
    if (root == null || node1 == null || node2 == null) {
      return null;
    }

    if (findPath(root, node1, path1) == false || findPath(root, node2, path2) == false) {
      return null;
    }

    int i, j;
    for (i = 0, j = 0; i < path1.size() && j < path2.size(); i++, j++) {
      if (path1.get(i).val != path2.get(j).val) {
        return path1.get(i - 1);
      }
    }
    return path1.get(i - 1);
  }

  private boolean findPath(TreeNode root, TreeNode node, List<TreeNode> path) {
    if (root == null) {
      return false;
    }
    
    path.add(root);

    if (root.val == node.val) {
      return true;
    }

    if ((root.left != null && findPath(root.left, node, path)) || 
        (root.right != null && findPath(root.right, node, path))) {
      return true;
    }
    
    path.remove(path.size() - 1);
    return false;
  }

  public static void main(String[] args) {
    LCA sol = new LCA();

    TreeNode root = new TreeNode(20);
    root.left = new TreeNode(8);
    root.right = new TreeNode(22);

    root.left.left = new TreeNode(4);
    root.left.right = new TreeNode(12);
    root.left.right.left = new TreeNode(10);
    root.left.right.right = new TreeNode(14);

    TreeNode ans = sol.lowestCommonAncestor(root, root.left.left, root);

    System.out.println(ans.val);
  }
}


Discussion:
Time complexity of LCA of binary tree is O(n). That is because we traverse the tree in DFS order and delete the unrelated numbers. So the time complexity is still O(n) not O(h). The space complexity of this solution is O(n) as well. Do be careful the time complexity of LCA for BST, which is O(h).

A better Solution:
A better solution could use Divide and Conquer solution.
public class LCA {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode node1, TreeNode node2) {
    if (root == null || root == node1 || root == node2) {
      return root;
    }

    // Divide
    TreeNode left = lowestCommonAncestor(root.left, node1, node2);
    TreeNode right = lowestCommonAncestor(root.right, node1, node2);

    // Conquer
    if (left != null && right != null) {
      return root;
    }

    if (left != null) {
      return left;
    }

    if (right != null) {
      return right;
    }

    return null;
  }

No comments:

Post a Comment