Binary Tree

Binary Tree typically can be regarded as two categories:

- Binary Tree

Tree node contains its value and two children: left and right

class TreeNode{
    int val;
    TreeNode left, right;
}

- Binary Search Tree

Binary Search Tree is similar with the binary tree in structure, but just one special character -- left child's value always less than root, while the right child has greater value than root.

Routines on Binary Tree:

• Traversal

  • Pre-order
  • In-order
  • Post-order
  • Level order

• Depth of Tree

  • Maximum Depth
  • Minimum Depth
  • Balanced Tree Check

• Sub-tree Check

• Find a Node and return the Path from Root to target Node

• Insert a Node in Tree

• Delete a Node in Tree (Difficult)

• Construct tree by in-order and pre-order

• Construct tree by in-order and post-order

Routines on Binary Search Tree

• Search range in Binary Search Tree
• Build Binary Search Tree
  • By Array
  • By Linked List

Trick

• Design recursion function with boolean type return
• Consider the in-order when meet the Binary Search Tree problem