Tree

Serialize and Deserialize Binary Search Tree

449. Serialize and Deserialize BST

If we look at the value of the pre-order traversal we get this:

rootValue (<rootValue) (<rootValue) (<rootValue) |separate line| (>rootValue) (>rootValue)

Because of BST's property: before the |separate line| all the node values are less than root value, all the node values after |separate line| are greater than root value. We will utilize this to build left and right tree.

Serialize and Deserialize Binary Tree

297. Serialize and Deserialize Binary Tree

One simple way is we do the pre-order traversal (treat the NULL node as a normal node) and recover the tree in the same way (pre-order). But, we have to know when we need to back up from leaf during tree construction -- every time a NULL node is encountered.

Verify BST Preorder Sequence

255. Verify Preorder Sequence in Binary Search Tree

To verify BST preorder sequence, the number num[i] must be greater than the ceiling on its left side.

*lowest we defined as the number < num[i] but the largest number from 0..i-1.

class Solution {
    /* using O(n) space stack
    public boolean verifyPreorder(int[] preorder) {
        Stack<Integer> path = new Stack<>();
        int lowest = Integer.MIN_VALUE;

        for(int num : preorder) {
            if(num<lowest) 
                return false;

            while(!path.isEmpty() && num > path.peek())
                lowest = path.pop();

            path.push(num);

        }

        return true;
    }
    */

    public boolean verifyPreorder(int[] preorder) {
        int lowest = Integer.MIN_VALUE;
        for(int i=0; i<preorder.length; i++) {
            if(preorder[i]<lowest) 
                return false;

            for(int j=i-1; j>=0 && preorder[j]<preorder[i]; j--)
                lowest = Math.max(lowest, preorder[j]);

        }

        return true;
    }



}

Iterative Pre-Order

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        while(root!=null || !stack.isEmpty()) {
            while(root!=null) {
                result.add(root.val);
                stack.push(root);
                root = root.left;
            }

            TreeNode temp = stack.pop();
            root = temp.right;
        }

        return result;
    }
}

Iterative In-order

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        while(root!=null || !stack.isEmpty()) {
            while(root!=null) {
                stack.push(root);
                root = root.left;
            }

            TreeNode temp = stack.pop();
            result.add(temp.val);
            root = temp.right;
        }

        return result;
    }
}

Iterative Post-order

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> result = new LinkedList<>();
        Stack<TreeNode> stack = new Stack<>();

        while(root!=null | !stack.isEmpty()) {
            while(root!=null) {
                stack.push(root);
                result.addFirst(root.val);
                root = root.right;
            }

            TreeNode temp = stack.pop();
            root = temp.left;
        }

        return result;
    }
}

Inorder Reverse Trasversal

Don't lose your sight to the typical inorder traversal Left Node Right. Some problem could be solved easily with reverse inorder traversal Right Node Left.

538. Convert BST to Greater Tree

Hybrid Pre-order Post-order in Single Problem

Depends on the need of the problem, we could put the work at both pre-order and post-order timing.

545. Boundary of Binary Tree

Full Binary Tree Node Position / Representation in Array

666. Path Sum IV

662. Maximum Width of Binary Tree

         0
     0       1
  0   1     2   3
0 1  2 3   4 5  6 7
Regardless whether these nodes exist:

the position of left child is always parent_pos * 2;
the position of right child is alwaysparent_pos * 2 + 1;
the position of parent is always child_pos / 2;

Morris Traversal