Boundary of Binary Tree
Medium · Trees · Tree · Depth-First Search · Binary Tree
Problem
The boundary of a binary tree is, in this order: the root, the left boundary, the leaves from left to right, and the right boundary in reverse (bottom-up). Each node appears once.
- The left boundary starts at the root's left child; it is empty if the root has no left child. From each boundary node, go to its left child if it has one, otherwise to its right child, until you reach a leaf. That leaf is not part of the left boundary.
- The right boundary is the same on the right side: start at the root's right child and prefer the right child at each step, stopping before the leaf.
- The leaves are the nodes with no children, not counting the root.
Given the root of a binary tree, return the values on its boundary in that order.
Examples
Input: root = [1,2,3,4,5,6,None,None,None,7,8] Output: [1,2,4,7,8,6,3]
The left boundary is [2]; the leaves are [4, 7, 8, 6]; the right boundary is [3], appended reversed.
Input: root = [1,None,2,3,4] Output: [1,3,4,2]
There is no left child, so the left boundary is empty. The leaves are [3, 4] and the right boundary is [2].
Input: root = [5] Output: [5]
A lone root is the whole boundary, listed once.
Constraints
- The number of nodes is in the range [1, 10^4]
- -1000 <= Node.val <= 1000
Approaches
- Classify every node by its path to the root — time O(n · h), space O(n)
Follow-up
The three parts can also be gathered in a single preorder pass that carries two flags, "on the left boundary" and "on the right boundary": add a node before its children when it is on the left boundary or a leaf, and after its children when it is on the right boundary, which produces the reversal for free.
Related problems
Start free on Cariara · Coding problems · System design studio
