[Leetcode] Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Solution :

1 2 3 4 5 6 7 8 9 10 11 12 13

public class Solution { public TreeNode inorderSuccessor(TreeNode root, TreeNode p) { if (root == null) return null; if (root.val <= p.val) { return inorderSuccessor(root.right, p); } else { TreeNode left = inorderSuccessor(root.left, p); return (left != null) ? left : root; } } }

[Leetcode] Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:

Input:

    2
   / \
  1   3

Output:
1

Example 2: 

Input:

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

Output:
7

Note: You may assume the tree (i.e., the given root node) is not NULL.

Solution : 

Most binary tree problems, in an interview setting can be solved by 5 kinds of traversals - inorder, postorder, preorder, BFS and DFS. I have decided to start a series of posts, where I shall be covering binary trees only. All the solutions, I provide will circle around these 5 traversal themes. My goal will be to establish a pattern which the readers can pick up. Hopefully, that will enable the readers in developing original thinking derived on these fundamentals for problems they may not have seen before.

In this particular problem, I will build up on the level order traversal (BFS) solution. This will use existing knowledge and help modify that code to come up with the new solution. 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

public class Solution { public int findBottomLeftValue(TreeNode root) { Queue<TreeNode> queue = new LinkedList<TreeNode>(); // Queue for // level order BFS traversal List<List<Integer>> wrapList = new LinkedList<List<Integer>>(); // wrapList stores the reverse level order solution // index 0 has the lowest level from left to right // so the first element of wrap list is the solution to the problem if(root == null) return 0; queue.offer(root); while(!queue.isEmpty()){ int levelNum = queue.size(); List<Integer> subList = new LinkedList<Integer>(); for(int i=0; i<levelNum; i++) { if(queue.peek().left != null) queue.offer(queue.peek().left); if(queue.peek().right != null) queue.offer(queue.peek().right); subList.add(queue.poll().val); } wrapList.add(0, subList); } return wrapList.get(0).get(0); } }