Binary Tree

Definition

A binary tree is a type of tree where each node has up to two children. We can have a ternary tree where each node has up to 3 children. Or a quadtree where each internal node has exactly 4 children.

public class TreeNode {
    int key;
    TreeNode leftChild;
    TreeNode rightChild;
    public TreeNode(int value) {
        key = value;
        leftChild = null; // not necessary 
        rightChild = null; // java does this during initialization
    }
}

or an alternative definition with array

public class TreeNode {
    public String name;
    public Node[] children;
}

DFS in Binary Tree

Binary Tree Traversal

Tree traversal is the process of visiting each node exactly once (a special case of graph traversal). There are three common ways to traverse them in depth-first order:

• Preorder - root, leftSubtree, rightSubtree

• Inorder - leftSubtree, root, rightSubtree

• Postorder - leftSubtree, rightSubtree, root

Example:

+    1
   /   \
  2     3
 / \
4   5

Preorder: 1 245 3
Inorder: 425 1 3
Postorder: 452 3 1

Traverse vs Divide & Conquer vs Iterative

• Traversal is usually implemented with recursion without a return value (only visiting)

• D&C is pretty much recursion on leftSubtree and rightSubtree then return the combined results

• Iterative implementation needs an explicit stack

Topics

Divide and Conquer

Traverse

Iterative

References

Wikipedia Tree Traversal