Review: Binary Tree Problems

Posted on January 22, 2018July 26, 2020 by braindenny

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.

Num	Problem	Summary
1	Binary Tree Level Order Traversal	LeetCode: Binary Tree Right Side View
2	Tree Traversal: Binary Tree Vertical Order Traversal	LeetCode: Binary Tree Vertical Order Traversal
3	Tree Traversal: Find Leaves of Binary Tree	Leetcode: Find Leaves of Binary Tree
4	Get binary tree height, width	LeetCode: Balanced Binary Tree
5	LCA – Lowest Common Ancestor of a binary Tree	LeetCode: Lowest Common Ancestor of a Binary Tree
6	Validate Binary Search Tree	LeetCode: Validate Binary Search Tree
7	Construct binary tree	LeetCode: Construct Binary Tree from Preorder and Postorder Traversal
8	Distribute Coins in Binary Tree	LeetCode: Distribute Coins in Binary Tree
9	Binary Tree Vertical Order Traversal	LeetCode: Binary Tree Vertical Order Traversal
10	Verify Preorder Sequence in Binary Search Tree	LeetCode: Verify Preorder Sequence in Binary Search Tree
11	Recursive + Greedy	LeetCode: Binary Tree Coloring Game
12	Binary tree + greedy	LeetCode: Binary Tree Cameras
13	Revert binary tree between left and right
14	binary tree serialization and deserialization
15	Morris tree trasversal
16	Find the next node of binary search tree
17	Count Complete Tree Nodes	LeetCode: Count Complete Tree Nodes
18	Binary Tree Upside Down	Leetcode: Binary Tree Upside Down
19	Closest Binary Search Tree Value II	Leetcode: Closest Binary Search Tree Value II

// 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.

Examine previous/next node for in-order traversal. Closest Binary Search Tree Value.
The most impressive problems to me:

See all binarytree problems: #binarytree.

See more blog posts.

Post Views: 3