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 non-recursive

non-recursive needs an explicit stack

Binary Search Tree

• Insert
• Find
• Remove
• Validate

BFS in Binary Tree

Binary tree level search

References

Wikipedia Tree Traversal