Validate Binary Search Tree (LeetCode Tree)

Question: Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Idea: In order traversal. If the previous node is larger or equal to the current node, return false and terminate the traversal.

Time: O(n) Space: O(lgn)

Code:

 public class Solution {  
   int prev;  
   boolean firstNode;  
   public boolean isValidBST(TreeNode root) {  
     firstNode=true;  
     return inorder(root);  
   }  
   public boolean inorder(TreeNode cur)  
   {  
     if(cur==null)  
       return true;  
     if(inorder(cur.left)==false)  
       return false;  
     if(!firstNode&&prev>=cur.val)  
       return false;  
     prev=cur.val;  
     firstNode=false;  
     if(inorder(cur.right)==false)  
       return false;  
     return true;  
   }  
 }  

Unique Binary Search Trees II (LeetCode Tree)

Question: Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Idea: Brute force recursion. Use every number  i as root, its left tree is (start,..., i-1) , its right tree is (i+1,...,end).

Time: O(n^2) Space: O(n)

Code:

 public class Solution {  
   public List<TreeNode> generateTrees(int n) {  
     return generate(1,n);  
   }  
   public List<TreeNode> generate(int start,int end)  
   {  
     List<TreeNode> result=new ArrayList<TreeNode>();  
     if(start>end)  
     {    
       result.add(null);  
       return result;  
     }  
     for(int i=start;i<=end;i++)  
     {  
       List<TreeNode> leftNode=generate(start,i-1);  
       List<TreeNode> rightNode=generate(i+1,end);  
       for(TreeNode l:leftNode)  
       {  
         for(TreeNode r:rightNode)  
         {  
           TreeNode cur=new TreeNode(i);  
           cur.left=l;  
           cur.right=r;  
           result.add(cur);  
         }  
       }  
     }  
     return result;  
   }  
 }  

Unique Binary Search Trees (LeetCode Tree)

Question: Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST's.

  1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

Idea: Do not consider 1, 2, 3, 4 as numbers, just consider them as variables or algebraic symbols, e.g. v1<v2<v3<v4<v5.., vi, ..,vn. The values make no sense in this problem.

If we pick vi as the root, the left subtree is formed by v1->vi-1, the right subtree is formed by vi+1->vn. Since the left subtree and the right subtree are independent, the number of different trees rooted at vi is  numLeft*numRight, where numLeft is the number of subtrees formed by v1->vi-1 (i-1 symbols), the numRight is the number of subtrees formed by vi+1->vn (n-i-1 symbols).

So the algorithm is obvious: for each symbol vi, use it as the root, get the numLeft*numRight=num(i-1 symbols)*num(n-i-1 symbols). Accumulate the total number of all the roots v1->vn, we can have the final result.

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public int numTrees(int n) {  
     int[] dp=new int[n+1];  
     dp[0]=1;  
     dp[1]=1;  
     for(int i=2;i<=n;i++)  
     {  
       for(int j=0;j<i;j++)  
       {  
         dp[i]+=dp[j]*dp[i-j-1];  
       }  
     }  
     return dp[n];  
   }  
 }  

Symmetric Tree (LeetCode Tree)

Question: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
    1
   / \
  2   2
 / \ / \
3  4 4  3
But the following is not:
    1
   / \
  2   2
   \   \
   3    3

Idea: Depth-first search. I used preorder traversal, compare current, then traverse (left.left, right.right) and (left.right, right.left) at the same time. Once a mismatch happens, stops and return.

Time: O(n) Space: O(lgn)

Code:

 public class Solution {  
   public boolean isSymmetric(TreeNode root) {  
     if(root==null)  
       return true;  
     return dfs(root.left,root.right);  
   }  
   public boolean dfs(TreeNode left, TreeNode right)  
   {  
     if(left==null||right==null)  
     {  
       if(left==null&&right==null)  
         return true;  
       return false;  
     }  
     if(left.val!=right.val)  
       return false;  
     return dfs(left.left,right.right)&&dfs(left.right,right.left);  
   }  
 }  

Sum Root to Leaf Numbers (LeetCode Tree)

Question: Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,
    1
   / \
  2   3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.

Idea: Depth-first search. Use a class member variable to record the result. Calculate the partial results along the search. Once a leaf is visited, update the total result.

Time: O(n) Space: O(lgn)

Code: 

 public class Solution {  
   int result;  
   public int sumNumbers(TreeNode root) {  
     result=0;  
     int lastSum=0;  
     dfs(lastSum,root);  
     return result;  
   }  
   public void dfs(int lastSum,TreeNode cur)  
   {  
     if(cur==null)  
       return;  
     if(cur.left==null&&cur.right==null)  
     {  
       result+=lastSum*10+cur.val;  
       return;  
     }  
     dfs(lastSum*10+cur.val,cur.left);  
     dfs(lastSum*10+cur.val,cur.right);  
   }  
 }  

Same Tree (LeetCode Tree)

Question: Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Idea: Any order traversal works. I used preorder traversal and use a class member variable to stop the traversal if the trees have been identified as different.

Time: O(n) Space: O(lgn)

Code:

 public class Solution {  
   boolean notSame;  
   public boolean isSameTree(TreeNode p, TreeNode q) {  
     notSame=false;  
     traverse(p,q);  
     return !notSame;  
   }  
   public void traverse(TreeNode p, TreeNode q)  
   {  
     if(notSame==true)  
       return;  
     if(p==null||q==null)  
     {  
       if(p!=null||q!=null)  
         notSame=true;  
       return;  
     }  
     if(p.val!=q.val)  
     {  
       notSame=true;  
       return;  
     }  
     traverse(p.left,q.left);  
     traverse(p.right,q.right);  
   }  
 }  

Recover Binary Search Tree (LeetCode Tree)

Question: Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.

Idea: In order traversal, use two class member variables to record the two abnormal nodes. Then swap their values.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   TreeNode v1,v2,prev;  
   public void recoverTree(TreeNode root) {  
     v1=null;  
     v2=null;  
     prev=new TreeNode(Integer.MIN_VALUE);  
     traversal(root);  
     int tmp=v1.val;  
     v1.val=v2.val;  
     v2.val=tmp;  
   }  
   public void traversal(TreeNode root)  
   {  
     if(root==null)  
       return;  
     traversal(root.left);  
     if(v1==null&&prev.val>=root.val)  
       v1=prev;  
     if(v1!=null&&prev.val>=root.val)  
       v2=root;  
     prev=root;  
     traversal(root.right);  
   }  
 }  

Populating Next Right Pointers in Each Node II (LeetCode Tree)

Question: Follow up for problem "Populating Next Right Pointers in Each Node".
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

Idea: Both depth-first search and breadth-first search work with the same time complexity. However, depth-first search is more space efficient. For depth-first search, always keeps track of the previous node to jump through the missing leaves. For breadth-first search, use a queue to remember each row.

Time: O(n) Space: O(1)

Code:

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

Populating Next Right Pointers in Each Node (LeetCode Tree)

Question: 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

Idea: Breadth-first search. If the node visited is not the last node in the level, connect it to the next node in the queue. Depth-first search method is the same, just remember the last node.

Time: O(n) Space: O(n) for breadth-first search, O(1) for depth-first search.

Breadth-first Search Code:

 public class Solution {  
   public void connect(TreeLinkNode root) {  
     if(root==null)   
       return;  
     Queue<TreeLinkNode> queue=new LinkedList<TreeLinkNode>();  
     queue.offer(root);  
     while(queue.isEmpty()==false)  
     {  
       int queueSize=queue.size();  
       for(int i=0;i<queueSize;i++)  
       {  
         TreeLinkNode cur=queue.poll();  
         if(i!=queueSize-1)  
         {  
           cur.next=queue.peek();  
         }  
         if(cur.left!=null)  
           queue.offer(cur.left);  
         if(cur.right!=null)  
           queue.offer(cur.right);  
       }  
     }  
   }  
 }  

Depth-first Search Code:

 public class Solution {  
   public void connect(TreeLinkNode root) {  
     if(root==null)  
       return;  
     TreeLinkNode parent=root;  
     TreeLinkNode next=parent.left;  
     while(parent!=null&&next!=null)  
     {  
       TreeLinkNode prev=null;  
       while(parent!=null)  
       {  
         if(prev==null)  
           prev=parent.left;  
         else  
         {  
           prev.next=parent.left;  
           prev=prev.next;  
         }  
         prev.next=parent.right;  
         prev=prev.next;  
         parent=parent.next;  
       }  
       parent=next;  
       next=parent.left;  
     }  
   }  
 }  

Path Sum II (LeetCode Tree)

Question: Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
return
[
   [5,4,11,2],
   [5,8,4,5]
]

Idea: Classic depth-first search problem. Keep going down the tree until reach a leaf, if the leaf's value equals the target, add the value to the path and add the path to the result. When the search goes up, do not forget to pop the current value from the path since the next search is in another route.

Time: O(n) Space: O(lgn)

Code:

 public class Solution {  
   public List<List<Integer>> pathSum(TreeNode root, int sum) {  
     List<List<Integer>> result=new ArrayList<List<Integer>>();  
     List<Integer> path=new ArrayList<Integer>();  
     dfs(result,path,root,sum);  
     return result;  
   }  
   public void dfs(List<List<Integer>> result,List<Integer> path, TreeNode cur, int target)  
   {  
     if(cur==null)  
       return;  
     if(cur.left==null&&cur.right==null)  
     {  
       if(cur.val==target)  
       {  
         path.add(cur.val);  
         result.add(new ArrayList<Integer>(path));  
         path.remove(path.size()-1);  
       }  
       return;  
     }  
     path.add(cur.val);  
     dfs(result,path,cur.left,target-cur.val);  
     dfs(result,path,cur.right,target-cur.val);  
     path.remove(path.size()-1);  
   }  
 }  

Path Sum (LeetCode Tree)

Question: Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

Idea: Brute force recursion.

Time: O(n) Space: O(lgn)

Code:

 public class Solution {  
   public boolean hasPathSum(TreeNode root, int sum) {  
     if(root==null)  
       return false;  
     if(root.left==null&&root.right==null&&root.val==sum)  
       return true;  
     int needed=sum-root.val;  
     return hasPathSum(root.left,needed)||hasPathSum(root.right,needed);  
   }  
 }  

Maximum Depth of Binary Tree (LeetCode Tree)

Question: Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Idea: Recursion. Very simple.

Time: O(n) Space: O(lgn)

Code:

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

Minimum Depth of Binary Tree (LeetCode Tree)

Question: Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Idea: Recursion. If the node is a leaf, return the result, otherwise return the accumulated depth from the children. I thought the code can be more clean if apply some math tricks, however, it will be much harder to be understood. So I just implement with the simplest logic. The time complexity is the same.

Time: O(n) Space: O(lgn)

Code:

 public class Solution {  
   public int minDepth(TreeNode root) {  
     if(root==null)  
       return 0;  
     if(root.left==null&&root.right==null)  
       return 1;  
     if(root.left==null)  
       return minDepth(root.right)+1;  
     if(root.right==null)  
       return minDepth(root.left)+1;  
     return Math.min(minDepth(root.left),minDepth(root.right))+1;  
   }  
 }  

Flatten Binary Tree to Linked List (LeetCode Tree)

Question:Given a binary tree, flatten it to a linked list in-place.
For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Idea: Recursion. Brute force and straightforward. Flatten the left tree, flatten the right tree, then connect the left tree with the right tree and set root.left to null.

Time: O(nlgn) (for each recursion, we need to traverse half of the tree) Space: O(n)

Code:

 public class Solution {  
   public void flatten(TreeNode root) {  
     if(root==null)  
       return;  
     flatten(root.left);  
     flatten(root.right);  
     TreeNode cur=root;  
     if(cur.left!=null)  
     {  
       cur=cur.left;  
       while(cur.right!=null)  
       {  
         cur=cur.right;  
       }  
       cur.right=root.right;  
       root.right=root.left;  
       root.left=null;  
     }  
   }  
 }  

Convert Sorted Array to Binary Search Tree (LeetCode Tree)

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

Idea: Recursion. The middle of the array is the tree root. Then build the left subtree based on the left half of the array [0...mid-1]. The right subtree is the right half [mid+1...end].

Time: O(n) Space: O(lgn) (Each recursion only pushes half of the tree to the stack)

Code:

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

Binary Tree Zigzag Level Order Traversal (LeetCode Tree)

Question: 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).
For example:
Given binary tree {3,9,20,#,#,15,7},
    3
   / \
  9  20
    /  \
   15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

Idea: Breadth-first search. Maintain a flag to reverse the direction of the next row.

Time: O(n) Space: O(1)

Code:

 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);  
     boolean reverse=false;  
     while(queue.isEmpty()==false)  
     {  
       int queueSize=queue.size();  
       List<Integer> row=new ArrayList<Integer>();  
       for(int i=0;i<queueSize;i++)  
       {  
         TreeNode cur=queue.poll();  
         if(reverse==true)  
         {  
           row.add(0,cur.val);  
         }  
         else  
         {  
           row.add(cur.val);  
         }  
         if(cur.left!=null)  
           queue.offer(cur.left);  
         if(cur.right!=null)  
           queue.offer(cur.right);  
       }  
       result.add(row);  
       reverse=!reverse;  
     }  
     return result;  
   }  
 }  

Binary Tree Upside Down (LeetCode Tree)

Question: Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
For example:
Given a binary tree {1,2,3,4,5},
    1
   / \
  2   3
 / \
4   5
return the root of the binary tree [4,5,2,#,#,3,1].
   4
  / \
 5   2
    / \
   3   1

Idea: Recursion. The new root is the left most node, which is also the new root of the flip of root's left substree. So we just need to keep track of the newRoot of flipping the left substrees and rotate the current level, left to root, root to right, right to left.

Time: O(n) Space: O(lgn) (each recursion call only pushes the left subtree to the stack)

Code:

 public class Solution {  
   public TreeNode UpsideDownBinaryTree(TreeNode root) {  
     if(root==null)  
       return null;  
     if(root.left==null&&root.right==null)  
       return root;  
     TreeNode newRoot=UpsideDownBinaryTree(root.left);  
     root.left.left=root.right;  
     root.left.right=root;  
     root.left=null;  
     root.right=null;  
     return newRoot;  
   }  
 }  

Binary Tree Preorder Traversal (LeetCode Tree)

Question: Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,2,3].

Idea: Recursion

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public List<Integer> preorderTraversal(TreeNode root) {  
     List<Integer> result=new ArrayList<Integer>();  
     visit(root,result);  
     return result;  
   }  
   public void visit(TreeNode root, List<Integer> result)  
   {  
     if(root==null)  
       return;  
     result.add(root.val);  
     visit(root.left,result);  
     visit(root.right,result);  
   }  
 }  

Binary Tree Postorder Traversal (LeetCode Tree)

Question: Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [3,2,1].

Idea: Recursion.

Time: O(n) Space: O(n)

Code:

 public class Solution {  
   public List<Integer> postorderTraversal(TreeNode root) {  
     List<Integer> result=new ArrayList<Integer>();  
     visit(root,result);  
     return result;  
   }  
   public void visit(TreeNode root,List<Integer> result)  
   {  
     if(root==null)  
       return;  
     visit(root.left,result);  
     visit(root.right,result);  
     result.add(root.val);  
   }  
 }  

Binary Tree Maximum Path Sum (LeetCode Tree)

Question: Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.

Idea: This problem seems quite hard since Java can not return multiple values in a function. However, by adding a class member variable, we can solve the problem as easy as in Python.

The path sum is consisted of three components: the maximum subroutine in the left subtree, the root.val, and the maximum subroutine in the right subtree.  Let us have a look two examples:

            1                                            1
       2           3                              2          1
    4   1                                       4   5
      (Example 1)                           (Example 2)

For the node 2 in example 1, it will better to contribute itself as a subroutine to form 4-2-1-3 the maximum. However, in example 2, the maximum path sum 4-2-5 is inside the subtree rooted at 2. So for any node x, there are two possible choices: 1) the maximum path sum is inside a subtree rooted at x, or  2) the subtree rooted at x will contribute a subroutine to x's parent. However, we do not know which choice is better. So we need to compare all of the choices to get the maximum.

The algorithm runs like this:
1) For each node x, calculate the maximum path sum inside the subtree rooted at x.
2) Update the result=max(result, this subtree's maximum)
3) return x's longest subroutine to x's parent for next comparison.

Time: O(n) Space: O(1)

Code:

 public class Solution {  
   int maxValue;  
   public int maxPathSum(TreeNode root) {  
     if(root==null)  
       return 0;  
     maxValue=Integer.MIN_VALUE;  
     maxPathDown(root);  
     return maxValue;  
   }  
   public int maxPathDown(TreeNode root)  
   {  
     if(root==null)  
       return 0;  
     int left=Math.max(maxPathDown(root.left),0);  
     int right=Math.max(maxPathDown(root.right),0);  
     maxValue=Math.max(maxValue,left+right+root.val);  
     return Math.max(left,right)+root.val;  
   }  
 }