Review: Binary Tree Problems

Many binary tree problems are about how to traversal it. In both recursive or non-recursive ways.

Binary Tree Traversal: Preorder, Inorder, Postorder, Level Order, Vertical Order, Right-Middle-Left, etc.

Only get the rightmost node at each level. Only get the leftmost node at each level, etc.

We might also see interesting requirements about updating binarytree. e,g, add a pointer to next, correct two nodes, delete a node, etc.

Basic Abstractions

Scenarios
Code Skeleton
Questions

// In-order traversal
// terminate when node is null
// function calls against both non-null pointers and null pointers
void inorder(node *r) {
  if (r == NULL)
    return;
  inorder(r->left);
  printf("%d", r->data);
  inorder(r->right);
}

// In-order traversal
// terminate when node is null or a leaf
// function calls against non-null pointers only
void inorder(node *r) {
  if (r == NULL)
    return;
  if (r->left != NULL) {
    inorder(r->left);
  }
  printf("%d", r->data);
  if (r->right != NULL) {
    inorder(r->right);
  }
}

Personally I like level-order (or BFS) very much.
(See all bfs problems: #bfs)

Q: How to time complexity for tree problems?

Q: Do you know the difference between level-order vs BFS(Breadth-first search)?

level-order traversal is the same as breadth-first traversal. 
There are many reasons to traverse something, it doesn't just have 
to be to search, as breadth-first search seems to imply, although 
many (or most) don't make that distinction and use the terms interchangeably.

From link: https://stackoverflow.com/questions/23576746/what-is-the-difference-between-breadth-first-searching-and-level-order-traversal

Examine previous/next node for in-order traversal. Closest Binary Search Tree Value.

The most impressive problems to me:

• Count Complete Tree Nodes
• Find Leaves of Binary Tree
• Binary Tree Vertical Order Traversal

See all binarytree problems: #binarytree.

• Review: Binary Tree Problems
• LintCode: The Biggest Score On The Tree
• LintCode: Binary Tree Maximum Node
• Leetcode: Validate Binary Search Tree
• Leetcode: Unique Binary Search Trees
• Leetcode: Trim a Binary Search Tree
• Leetcode: Sum Root to Leaf Numbers
• Leetcode: Sum of Left Leaves
• Leetcode: Subtree of Another Tree
• Leetcode: Smallest Subtree with all the Deepest Nodes
• Leetcode: Serialize and Deserialize BST
• Leetcode: Serialize and Deserialize Binary Tree
• Leetcode: Second Minimum Node In a Binary Tree
• Leetcode: Search in a Binary Search Tree
• Leetcode: Same Tree
• Leetcode: Recover Binary Search Tree
• Leetcode: Range Sum of BST
• Leetcode: Quad Tree Intersection
• Leetcode: Populating Next Right Pointers in Each Node II
• Leetcode: Populating Next Right Pointers in Each Node
• Leetcode: Path Sum IV
• Leetcode: Path Sum III
• Leetcode: Path Sum II
• Leetcode: Path Sum
• Leetcode: Path In Zigzag Labelled Binary Tree
• Leetcode: Most Frequent Subtree Sum
• Leetcode: Minimum Depth of Binary Tree
• Leetcode: Minimum Cost Tree From Leaf Values
• Leetcode: Minimum Absolute Difference in BST
• Leetcode: Merge Two Binary Trees
• Leetcode: Maximum Width of Binary Tree
• Leetcode: Maximum Depth of Binary Tree
• Leetcode: Maximum Binary Tree
• Leetcode: Lowest Common Ancestor of Deepest Leaves
• Leetcode: Lowest Common Ancestor of a Binary Search Tree
• Leetcode: Longest Univalue Path
• Leetcode: Largest BST Subtree
• Leetcode: Invert Binary Tree
• Leetcode: Insufficient Nodes in Root to Leaf Paths
• Leetcode: Insert into a Binary Search Tree
• Leetcode: Flatten Binary Tree to Linked List
• Leetcode: Find Mode in Binary Search Tree
• Leetcode: Find Leaves of Binary Tree
• Leetcode: Find Duplicate Subtrees
• Leetcode: Equal Tree Partition
• Leetcode: Diameter of Binary Tree
• Leetcode: Delete Node in a BST
• Leetcode: Cousins in Binary Tree
• Leetcode: Count Complete Tree Nodes
• Leetcode: Convert Sorted List to Binary Search Tree
• Leetcode: Convert Sorted Array to Binary Search Tree
• Leetcode: Convert BST to Greater Tree
• Leetcode: Construct String from Binary Tree
• Leetcode: Construct Quad Tree
• Leetcode: Construct Binary Tree from Preorder and Postorder Traversal
• Leetcode: Complete Binary Tree Inserter
• Leetcode: Closest Binary Search Tree Value II
• Leetcode: Closest Binary Search Tree Value
• Leetcode: Boundary of Binary Tree
• Leetcode: Binary Trees With Factors
• Leetcode: Binary Tree Vertical Order Traversal
• Leetcode: Binary Tree Upside Down
• Leetcode: Binary Tree Tilt
• Leetcode: Binary Tree Right Side View
• Leetcode: Binary Tree Pruning
• Leetcode: Binary Tree Preorder Traversal
• Leetcode: Binary Tree Postorder Traversal
• Leetcode: Binary Tree Paths
• Leetcode: Binary Tree Maximum Path Sum
• Leetcode: Binary Tree Longest Consecutive Sequence II
• Leetcode: Binary Tree Longest Consecutive Sequence
• Leetcode: Balanced Binary Tree
• Leetcode: Average of Levels in Binary Tree
• Leetcode: All Possible Full Binary Trees
• Leetcode: Add One Row to Tree
• Find Largest Value in Each Tree Row

See more blog_posts.