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 |

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

- Review: Binary Tree Problems
- LintCode: The Biggest Score On The Tree
- LintCode: Binary Tree Maximum Node
- Leetcode: Verify Preorder Sequence in Binary Search Tree
- LeetCode: Validate Binary Tree Nodes
- 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

See more blog posts.