Binary trees
A linked list is a chain: each node holds a value and a link to the next node. In a binary tree each node holds a value and links to at most two nodes below it, its left child and its right child. In this lesson a tree is the input, and we write functions that answer questions about it, such as how tall it is or how far apart its two farthest nodes are.
In this tree:
- The node at the top, 8, is the root. Every other node has one parent, the node directly above it.
- A node has two children, one child or none. It matters which side a child is on: 10 has only a right child, 14, and if 14 were the left child of 10, this would be a different tree.
- A node with no children is a leaf: 1, 6 and 14 here.
- The subtree of a node is the node together with all the nodes below it. The subtree of 3 is 3, 1 and 6.
- The root is on level 0, its children on level 1 and their children on level 2.
- The height of a tree is the number of nodes on the longest path from the root down to a leaf, 3 for this tree.
A subtree is a binary tree in its own right. So a binary tree is a root with up to two smaller binary trees below it, its left subtree and its right subtree. Most functions in this lesson follow that structure: they do a little work at one node and call themselves on its two subtrees.
A binary tree in code
In code, a node is an object with three fields: its value val, and the links left and right to its children. A missing child is None.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left # a TreeNode, or None for a missing child
self.right = rightA problem statement cannot show linked objects, so LeetCode writes a tree as a list: the values level by level, each level from left to right, with null where a child is missing. Our tree is [8,3,10,1,6,null,14]:
null is the missing left child of 10.The list writes nothing below a null, because a missing node has no children. In [1,null,2,3] the root 1 has no left child, written null, and its right child is 2. The next level can only hold the children of 2, so 3 is the left child of 2. A null at the end of a list is left off, which is why the missing right child of 2 is not written.
Preorder, inorder and postorder
Visiting every node of a tree once, in some order, is called a traversal. The usual way to write one is a recursive function. The function below prints the value of the node it is called on, then calls itself on the left child, then on the right child. Called on a missing child, it returns without doing anything:
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def preorder(node):
if node is None:
return
print(node.val, end=' ')
preorder(node.left)
preorder(node.right)
root = TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(10, None, TreeNode(14)))
preorder(root)
print()The line that starts root = builds our tree by nesting TreeNode calls, with None for the missing left child of 10, and the program prints 8 3 1 6 10 14.
The call on 8 prints 8 and calls the function on 3. That call returns only after the whole subtree of 3 has been printed, which gives 3, 1 and 6. Then the call on 8 moves on to its right child, and 10 and 14 follow.
A missing child is treated as an empty tree, a tree with no nodes, and the empty tree is the base case of the recursion: the first two lines of the function return at once when node is None. So a leaf such as 1 still calls the function on its two missing children, and each of those calls returns without printing anything.
The order of the output depends on where the line that prints sits. It can go before the two calls, between them or after them, and each order has a name:
- In preorder the node comes first, then its left subtree, then its right subtree.
- In inorder the left subtree comes first, then the node, then the right subtree.
- In postorder the left subtree comes first, then the right subtree, then the node.
Our function prints in preorder. Here is our tree in each order, with the root highlighted and each of its subtrees kept together:
The inorder row came out sorted because of how the values of this tree were placed: at every node, the values in the left subtree are smaller and the values in the right subtree are larger. A tree kept that way is called a binary search tree. In other trees the inorder is not sorted. On the tree [1,null,2,3] it gives 1, 3, 2: the root has no left child, so 1 comes first, and its right subtree is 2 with the left child 3, which gives 3 and then 2.
LeetCode asks for the inorder as a list:
You get the root of a binary tree. Return the values of its nodes in inorder, as a list.
Constraints
- The tree has between and nodes
-
Node.val
Sample 1 · Input
root = [1,null,2,3]
Output
[1,3,2]
Sample 2 · Input
root = [1,2,3,4,5,null,8,null,null,6,7,9]
Output
[4,2,6,5,7,1,3,9,8]
Sample 3 · Input
root = []
Output
[]
Sample 4 · Input
root = [1]
Output
[1]
The first sample is the tree we just walked. The solution is the function above with the line that prints moved between the two calls, and it appends each value to a list instead of printing it. The list answer belongs to the outer function, so every call of visit appends to the same list.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def inorder_traversal(root):
answer = []
def visit(node):
if node is None:
return
visit(node.left)
answer.append(node.val)
visit(node.right)
visit(root)
return answer
# the samples [1,null,2,3] and [1]
print(inorder_traversal(TreeNode(1, None, TreeNode(2, TreeNode(3)))))
print(inorder_traversal(TreeNode(1)))Prints [1, 3, 2] and [1].
A traversal makes one call for every node and one for every missing child: 13 calls on our tree, which has six nodes and seven missing children. Every tree of nodes has missing children. Its nodes have places for a child, every node except the root fills one of those places, and that leaves of them empty. So a traversal makes calls and runs in time.
The three orders step by step
This widget runs a traversal of our tree one call at a time, with the output so far and the calls that are still open. Switching the order changes only the moment a node is recorded: the calls take the same route through the tree in all three.
The widget's input box accepts another tree in the list notation, with one difference: every position is written out, so the two missing children of a null are written as null as well. [1,null,2,3] is typed as 1, null, 2, null, null, 3.
The height of a tree
Many questions about a tree ask for a single number, such as how many nodes it has or how tall it is. A function that answers one returns a number from each call, and each call works out its own number from what the calls on its two children return. We start with the height.
You get the root of a binary tree. Return its maximum depth: the number of nodes on the longest path from the root down to a leaf.
Constraints
- The tree has between and nodes
-
Node.val
Sample 1 · Input
root = [3,9,20,null,null,15,7]
Output
3
Sample 2 · Input
root = [1,null,2]
Output
2
In this drawing of the first sample, the height of each subtree is written under its top node:
The longest paths from the root down to a leaf are 3, 20, 15 and 3, 20, 7. Each has three nodes, so the answer is 3. LeetCode calls this number the maximum depth. It counts the nodes on the path, so it is the height as we defined it, one more than the level of the deepest node.
The numbers under the nodes follow one rule. The longest path down from a node is the node followed by the longer of the longest paths down from its two children. So the height of a tree is 1, for the root, plus the larger of the heights of its two subtrees, and the height of an empty tree is 0:
For the leaf 9 the rule gives , for 20 it gives , and for the root . The function is the rule written as code:
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def max_depth(root):
if root is None:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
# the samples [3,9,20,null,null,15,7] and [1,null,2]
print(max_depth(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))))
print(max_depth(TreeNode(1, None, TreeNode(2))))Prints 3 and 2.
The call on 20 reaches max only after the calls on 15 and 7 have returned, so both subtree heights are known when it compares them. The node's own work comes after its two calls, as in a postorder traversal, and like any traversal the function takes time.
Other values come from the same function with a different last line. Returning 1 plus the sum of the two subtree answers counts the nodes: for this tree, 1 for the root, 1 for the subtree of 9 and 3 for the subtree of 20.
The height also tells you how deeply the calls of a recursive function nest. While the function is at a node, the calls on all the nodes above it, up to the root, are still open. So at the deepest leaf there are as many open calls as the tree is high.
How high can a tree of nodes be? If every node has a single child, the tree is a chain like a linked list, and nodes have height . If every level is full, the levels hold 1, 2, 4, 8 nodes and so on, and 20 levels hold nodes, so a million nodes fit in 20 levels. A recursive function on that tree has about 20 calls open at a time, and on a chain of a million nodes it has a million.
The diameter of a tree
The height measures the longest path that starts at the root and goes down. The diameter is the longest path between any two nodes, wherever they are in the tree.
You get the root of a binary tree. Return the length of its diameter: the number of edges on the longest path between any two nodes. The path does not have to pass through the root.
Constraints
- The tree has between and nodes
-
Node.val
Sample 1 · Input
root = [1,2,3,4,5]
Output
3
Sample 2 · Input
root = [1,2]
Output
1
A path follows the links between parents and children and visits no node twice. Its length is counted in edges, the links it uses, so a path through four nodes has length 3. In the first sample one longest path is 4, 2, 1, 3:
The path 5, 2, 1, 3 is equally long, and the answer is 3.
A path goes up from one end, reaches a highest node, and goes down to the other end. We say the path bends at its highest node. The path 4, 2, 1, 3 bends at the root, and the shorter path 4, 2, 5 bends at 2. For a path that only goes down, the highest node is its top end.
The longest path that bends at a given node goes as deep as it can on each side. The left subtree of the root has height 2, so the path can use two edges on that side: one from the root to its left child, and one more down to a leaf. Each side adds as many edges as its subtree is high, so the longest path that bends at a node has
At the root of the sample this is , and at node 2 it is . Every path bends at some node, so the diameter is the largest of these sums over all nodes.
The sums lead straight to a program: at every node, call max_depth on both children and add the results. It reads the same nodes many times, because each call of max_depth reads a whole subtree. On a chain of nodes the calls for the root read the nodes below it, the calls for the next node read , and so on. For the 10,000 nodes this problem allows, that is
about half a second at roughly simple operations a second. That may still pass here. CSES Tree Diameter asks this for general trees of up to 200,000 nodes, and there the same sum is 19,999,900,000 reads, about 200 seconds.
A single call of max_depth on the root computes the height of every subtree on its way, and returns only the last of them. So one walk is enough if each call does two things with its children's heights. It adds them, which gives the length of the longest path that bends at its node, and keeps the sum if it is the largest so far. Then it returns 1 plus the larger of the two, the height of its own subtree, to its parent.
The table lists the calls on the first sample in the order they finish:
| Node | Left height | Right height | Longest path that bends here | Returns |
|---|---|---|---|---|
| 4 | 0 | 0 | 0 | 1 |
| 5 | 0 | 0 | 0 | 1 |
| 2 | 1 | 1 | 2 | 2 |
| 3 | 0 | 0 | 0 | 1 |
| 1 | 2 | 1 | 3 | 3 |
In code, the best length is a variable outside the recursive function:
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def diameter_of_binary_tree(root):
best = 0
def height(node):
nonlocal best
if node is None:
return 0
left = height(node.left)
right = height(node.right)
best = max(best, left + right) # the longest path that bends here
return 1 + max(left, right) # the height of this subtree
height(root)
return best
# the samples [1,2,3,4,5] and [1,2]
print(diameter_of_binary_tree(TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))))
print(diameter_of_binary_tree(TreeNode(1, TreeNode(2))))Prints 3 and 1.
The sum goes into best, and the function returns the height. A longer path through the parent reaches this node along the link from the parent and can go down only one side from here, so the height is all the parent can use. The path that bends here uses both sides, and no path through the parent can extend it. The line nonlocal best lets the inner function assign to the outer variable. The walk reads each node once, so it takes time.
The walk step by step
The Postorder tab of the widget runs this walk. A finished node shows the height it returned, and the line under the tree gives the longest path so far and the node where it bends.
Typing 1, 2, null, 3, 4, null, null, 5, null, null, 6 into the box gives a tree whose longest path, 5, 3, 2, 4, 6, bends at 2, below the root.
Height-balanced trees
The diameter walk returns the height of each subtree to its parent and keeps the longest path found so far on the side. If it keeps something else on the side, the same walk answers other questions. One of them is whether a tree is height-balanced, which means that at every node the heights of the left and right subtrees differ by at most 1.
You get the root of a binary tree. Return true if it is height-balanced and false otherwise.
Constraints
- The tree has between and nodes
-
Node.val
Sample 1 · Input
root = [3,9,20,null,null,15,7]
Output
true
Sample 2 · Input
root = [1,2,2,3,3,null,null,4,4]
Output
false
Sample 3 · Input
root = []
Output
true
Balance matters because a balanced tree cannot be tall. To see how tall a balanced tree of a million nodes can be, count the fewest nodes a balanced tree of each height needs. At height , one subtree of the root has height , and balance keeps the other at height or more. So the fewest is 1 node for the root, plus the fewest for height , plus the fewest for height . Heights 1, 2, 3 and 4 need 1, 2, 4 and 7 nodes, since and . Continuing the same sums gives 832,039 nodes for height 28 and 1,346,268 for height 29.
So a balanced tree of a million nodes has height at most 28, close to the 20 of a tree with full levels and far from the million of a chain. A binary search tree is fast only while it stays short like this, because each of its operations walks one path down from the root.
The second sample, drawn with the height of each subtree under its top node, breaks the rule in one place:
At the root the two heights are 3 and 1. They differ by 2, so the tree is not balanced, although every other node passes.
The diameter walk already has both heights at every node. To check balance, the function below compares them where the diameter walk added them, and a flag records any node that fails:
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def is_balanced(root):
balanced = True
def height(node):
nonlocal balanced
if node is None:
return 0
left = height(node.left)
right = height(node.right)
if abs(left - right) > 1: # this node fails the check
balanced = False
return 1 + max(left, right)
height(root)
return balanced
# the samples [3,9,20,null,null,15,7] and [1,2,2,3,3,null,null,4,4]
print(is_balanced(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))))
print(is_balanced(TreeNode(1, TreeNode(2, TreeNode(3, TreeNode(4), TreeNode(4)), TreeNode(3)), TreeNode(2))))Prints True and False.
The comparison has to run at every node, because a tree can fail below a root whose own two heights are equal. The Common mistakes part shows one.
Deeper read: the path with the largest sum
A harder problem of the same kind uses the values in the nodes. Some of them can be negative, and the task is to find the path whose values add up to the most.
You get the root of a binary tree. A path is a sequence of nodes joined by edges, with each node used at most once; it has at least one node and does not have to pass through the root. Return the largest sum of node values along any path.
Constraints
- The tree has between and nodes
-
Node.val
Sample 1 · Input
root = [1,2,3]
Output
6
Sample 2 · Input
root = [-10,9,20,null,null,15,7]
Output
42
In the first sample the best path is 2, 1, 3. The second sample is the Maximum Depth tree with at the root, and its best path, 15, 20, 7, leaves the root out.
The walk is the diameter walk with sums of values in place of heights. Each call returns the largest sum of a path that starts at its node and goes down, which the code calls the gain of the node. A path that bends at a node is the node plus at most one downward path on each side, so its largest sum is the node's value plus the most that each side can add.
A height is never negative, but a gain can be, and a side with a negative gain makes the path worse than leaving that side out. So each child's gain is replaced by 0 when it is negative, which stands for a path that does not enter that subtree. In [1,-2,3] the best path is 1, 3 with sum 4, and taking the as well would lower it to 2.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def max_path_sum(root):
best = root.val
def gain(node): # largest sum of a path going down from node
nonlocal best
if node is None:
return 0
left = max(gain(node.left), 0) # a negative side is left out
right = max(gain(node.right), 0)
best = max(best, node.val + left + right) # the best path that bends here
return node.val + max(left, right)
gain(root)
return best
# the samples [1,2,3] and [-10,9,20,null,null,15,7]
print(max_path_sum(TreeNode(1, TreeNode(2), TreeNode(3))))
print(max_path_sum(TreeNode(-10, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))))Prints 6 and 42.
On the second sample the leaves return 9, 15 and 7. At 20 the best path that bends there sums to , and 20 returns . At the root the best path that bends there sums to , so the answer stays 42.
best starts at the root's value and not at 0, because a path has at least one node. For the single node [-3] the answer is .
The lowest common ancestor of two nodes
The ancestors of a node are the nodes on the path from it up to the root: its parent, the parent of its parent, and so on. In this problem the node itself counts as one of its ancestors too. Two nodes always share at least one ancestor, the root, and the problem asks for the lowest one they share.
You get the root of a binary tree and two different nodes p and q in it. Return their lowest common ancestor: the node farthest from the root that is an ancestor of both. A node counts as its own ancestor.
Constraints
- The tree has between and nodes
-
Node.val, all values distinct pandqare different and both in the tree
Sample 1 · Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output
3
Sample 2 · Input
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output
5
Sample 3 · Input
root = [1,2], p = 1, q = 2
Output
1
The first two samples share this tree:
In the first sample, 5 and 1 are the two children of 3, so their only common ancestor is 3. In the second, the ancestors of 4 are 4, 2, 5 and 3, and the ancestors of 5 are 5 and 3. The common ones are 5 and 3, and the lower one is 5.
The direct method searches the subtree of every node for p and for q, and keeps the lowest node whose subtree holds both. Each search can read a whole subtree. On a chain of the 100,000 nodes this problem allows, with p at the bottom, the searches for p alone read
That is about 50 seconds of work. As with the diameter, one walk is enough when every call reports what it found in its own subtree. A call on a node returns one of three things:
- nothing, if neither
pnorqis in the subtree; porq, if exactly one of them is in the subtree;- their lowest common ancestor, if both are in the subtree.
In code, a call whose node is p or q returns that node at once. Otherwise it calls itself on both children. If both calls return a node, p is on one side and q on the other, so the current node is their lowest common ancestor. If only one call returns a node, that node is passed up unchanged.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def lowest_common_ancestor(root, p, q):
if root is None or root is p or root is q:
return root
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
if left and right: # p is on one side and q on the other
return root
return left or right
# the sample tree [3,5,1,6,2,0,8,null,null,7,4]
four = TreeNode(4)
five = TreeNode(5, TreeNode(6), TreeNode(2, TreeNode(7), four))
one = TreeNode(1, TreeNode(0), TreeNode(8))
root = TreeNode(3, five, one)
print(lowest_common_ancestor(root, five, one).val)
print(lowest_common_ancestor(root, five, four).val)Prints 3 and 5.
A call that reaches p returns at once, without looking for q below it. That is still right when q is below p: then p is an ancestor of q, so p itself is their lowest common ancestor, and the walk passes p up to the root as the answer. In the second sample the call on 5 returns 5 without reaching 4, the call on 1 finds nothing, and the root passes 5 up. Each node is read at most once, so the walk takes time.
Rebuild a tree from its preorder and inorder
A traversal turns a tree into a list. This problem goes the other way: it gives two traversals of a tree and asks for the tree.
You get two lists, preorder and inorder, which are the preorder and inorder traversals of the same binary tree. All values are distinct. Build the tree and return its root.
Constraints
- , where is the length of both lists
- each value , all distinct
Sample 1 · Input
preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output
[3,9,20,null,null,15,7]
Sample 2 · Input
preorder = [-1], inorder = [-1]
Output
[-1]
One traversal does not determine the tree. A root 1 with a left child 2 and a root 1 with a right child 2 are different trees with the same preorder, 1, 2. Their inorders differ: 2, 1 and 1, 2.
With both lists we can read the tree off. The first sample has the preorder 3, 9, 20, 15, 7 and the inorder 9, 3, 15, 20, 7. Preorder starts with the root, so the root is 3. Inorder has the left subtree before the root and the right subtree after it. The values are distinct, so 3 appears once in the inorder list, and finding it splits the list into 9 on the left and 15, 20, 7 on the right.
Preorder holds the root, then the whole left subtree, then the whole right subtree. The left subtree has one value, so it is the 9 after the root, and the last three values are the right subtree.
Each side is the same problem on a smaller tree. The right side has these two lists:
A side with one value is a leaf, and a side with no values is an empty subtree, where the recursion stops. Each split finds the root of one subtree, so the whole tree takes one split per node.
Deeper read: the split in code
Copying each side out of the lists at every split would cost time and memory, so the program describes a side by three numbers: pre_start, where its preorder begins, and lo and hi, where its inorder begins and ends, with hi one past the last value.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def build_tree(preorder, inorder):
where = {value: i for i, value in enumerate(inorder)}
def make(pre_start, lo, hi):
if lo == hi: # no values: an empty subtree
return None
value = preorder[pre_start] # preorder begins with the root
mid = where[value] # the root's position in inorder
left_size = mid - lo
left = make(pre_start + 1, lo, mid)
right = make(pre_start + 1 + left_size, mid + 1, hi)
return TreeNode(value, left, right)
return make(0, 0, len(inorder))
def postorder(node):
if node is None:
return []
return postorder(node.left) + postorder(node.right) + [node.val]
print(postorder(build_tree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7])))
print(postorder(build_tree([-1], [-1])))Prints [9, 15, 7, 20, 3] and [-1].
The root is preorder[pre_start] and mid is its position in inorder, so the left subtree has mid - lo values. Its preorder begins right after the root, and the preorder of the right subtree begins after those left_size values. To check the result, the program prints the postorder of the tree it built.
where is a dictionary from each value to its position in inorder, so each root is found in one lookup and the rebuild takes time. Without it, each root would be found by scanning its side of the inorder list. On a chain of 3,000 nodes in which every node has only a left child, the root is the last value of its side every time, and the scans read values, about . That passes at this size and grows quickly beyond it.
Level order with a queue
Some questions need the nodes level by level: the root, then its children, then their children, each level from left to right, the way you read the lines of a page. The recursive functions above do not give that order, because each of them finishes one whole subtree before it starts the next.
You get the root of a binary tree. Return its values level by level, each level read from left to right, as one list per level.
Constraints
- The tree has between and nodes
-
Node.val
Sample 1 · Input
root = [3,9,20,null,null,15,7]
Output
[[3],[9,20],[15,7]]
Sample 2 · Input
root = [1]
Output
[[1]]
Sample 3 · Input
root = []
Output
[]
The first sample is the Maximum Depth tree again. Its levels are 3, then 9 and 20, then 15 and 7.
This walk uses no recursion. It keeps the nodes that are waiting to be visited in a queue, which hands them back first in, first out. The queue starts with the root. Each step takes the node at the front, records it, and adds its children at the back, the left child first. The children wait behind every node already in the queue, so the nodes leave the queue level by level, and from left to right within a level.
To report each level as its own list, the loop works in rounds. When a round begins, the queue holds exactly one level:
[3,9,20,null,null,15,7], front first.The round reads the length of the queue and takes that many nodes. The children they add are the next level, which is what the queue holds when the next round begins. Each node enters the queue once and leaves it once, so the walk takes time.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def level_order(root):
output, queue = [], deque([root] if root else [])
while queue:
level = []
for _ in range(len(queue)): # only the nodes of this level
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
output.append(level)
return output
# the samples [3,9,20,null,null,15,7] and []
print(level_order(TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))))
print(level_order(None))Prints [[3], [9, 20], [15, 7]] and [].
The queue step by step
The widget shows the queue under the tree as the walk takes one node per step.
Deeper read: deep trees and an explicit stack
The recursive functions in this lesson open one call per level of the tree, and Python limits how deep calls can nest. sys.getrecursionlimit() reports the limit, 1,000 by default. A tree of a million nodes with full levels is only 20 levels deep, but a chain of 5,000 nodes is 5,000 levels deep, and max_depth stops on it with a RecursionError.
The level-order loop has no such limit, because the nodes it has yet to visit wait in a queue, which can grow as large as memory allows.
With a stack in place of its queue, the same loop goes deep first, as the recursive functions do. A stack hands back the node that was added last, so the children of a node come out before the nodes that were already waiting, and the loop finishes a subtree before it moves on. The loop below pops a node, records it, and pushes its right child and then its left child. The left child is pushed last, so it comes out first, and the nodes are recorded in preorder. Inorder and postorder need loops with more bookkeeping.
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def preorder_iterative(root):
output, stack = [], [root] if root else []
while stack:
node = stack.pop()
output.append(node.val)
if node.right: # pushed first, so it comes out second
stack.append(node.right)
if node.left:
stack.append(node.left)
return output
# the tree [8,3,10,1,6,null,14] from the first part
print(preorder_iterative(TreeNode(8, TreeNode(3, TreeNode(1), TreeNode(6)), TreeNode(10, None, TreeNode(14)))))Prints [8, 3, 1, 6, 10, 14], the preorder from the second part.
Common mistakes
Counting nodes where the problem counts edges.
- Where it breaks
- Recording
left + right + 1for the path that bends at each node counts the nodes on the path. The diameter of[1,2,3,4,5]then comes out as 4, for the nodes 4, 2, 1, 3, where the answer is 3 edges. - The fix
- Check the function on a tree of two nodes, which has one edge. Diameter of Binary Tree counts edges, and Maximum Depth counts nodes.
Checking balance only at the root.
- Where it breaks
- In
[1,2,2,3,null,null,3,4,null,null,4]both subtrees of the root have height 3, so a check at the root alone saystrue. The left 2 has a left subtree of height 2 and no right subtree, so the answer isfalse. - The fix
- Compare the two heights at every node, as
is_balanceddoes.
Recall A tree has the preorder 1, 2, 4, 5, 3 and the inorder 4, 2, 5, 1, 3. What are its height and its postorder?
The root is 1, the first preorder value. In the inorder list 4, 2, 5 come before the 1 and 3 comes after it, so the left subtree has three nodes and the right subtree is the single node 3. The left subtree has the preorder 2, 4, 5 and the inorder 4, 2, 5, so its root is 2, with 4 on the left and 5 on the right. The height is 3, along 1, 2, 4, and the postorder is 4, 5, 2, 3, 1.
Further reading
- USACO Guide, SilverIntroduction to Tree Algorithms(opens in a new tab)
The vocabulary for trees whose nodes can have any number of children, the three traversal orders, and subtree sizes computed by one recursive function on CSES Subordinates.
- Antti Laaksonen, free PDFCompetitive Programmer’s Handbook, chapter 14(opens in a new tab)
Tree traversal and the diameter by dynamic programming over subtrees, then section 14.4 on binary trees, the three orders, and which pairs of orders determine a tree.
- MIT 6.006, Spring 2020Lecture 6: Binary Trees, Part 1(opens in a new tab)
Defines traversal order, subtree height and depth, then builds successor, predecessor, insertion and deletion on top of them in . It counts height in edges, one less than the height in this lesson.
- Pat MorinOpen Data Structures, Chapter 6: Binary Trees(opens in a new tab)
The chapter opening counts the missing children of a tree; Section 6.1 computes size, height and depth with recursive functions, then traverses a tree without recursion, by following parent pointers or level by level with a queue. Parts of this page adapt this chapter’s text, licensed CC BY 2.5 Canada (creativecommons.org/licenses/by/2.5/ca), with changed wording, examples and code.
- OI Wiki, in Chinese树基础(opens in a new tab)
The tree vocabulary of this lesson with diagrams, special kinds of binary trees, and the three recursive traversal orders and level order.