Binary tree traversal algorithm¶
Overview¶
Binary tree as a basic data structure, traversal algorithm as a basic algorithm, the combination of the two is of course a classic combination. Many questions will have the figure of ta, some are directly asked about the traversal of the binary tree, and some are asked indirectly. For example, if you want to find a node in the tree that meets the condition, you are indirectly inspecting the traversal of the tree, because you need to traverse the tree if you want to find the point that meets the condition.
If you have mastered the traversal of binary trees, then maybe other complex trees are not far away for you
The traversal of binary numbers mainly includes left, root and right traversal
and level traversal
. The left, root and right belong to DFS, and the level traversal belongs to BFS. Both DFS and BFS have their own applications, such as leetcode 301 and 609.
DFS can use the stack to simplify operations, and in fact, the tree itself is a recursive data structure, so recursion and stack are two key points for DFS
.
DFS diagram:
The key point of BFS is how to record whether each level is traversed`. We can use a flag to indicate the end of the current level.
First of all, whether it is traversal in left-root or right-order, only the position of the root node is changed, and the order of left and right nodes is always from left to right. For example, preorder traversal means that the root is in front, that is, the root, left and right
. The Inorder means that the root is in the middle, that is, the left root and right
. Post-order means that the root is at the back, that is, the left and right root
.
Below we explain in turn:
Preorder traversal¶
Related questions 144.binary-tree-preorder-traversal
The preorder traversal order is root-left-right
The idea is:
-
Put the root node on the stack first
-
Pop an element from the stack, and push the left node and right node into the stack in turn
-
Repeat step 2
Summary: A typical recursive data structure, a typical algorithm that uses a stack to simplify operations.
In fact, from a macro perspective: visit the left chain from top to bottom, and then visit the right chain from bottom to top
. If you write from this perspective, the algorithm will be different. From top to bottom, we can directly access recursively, and from bottom to top, we can easily do it with the help of the stack.
The whole process is roughly like this:
One advantage of this kind of thinking is that you can unify the tree traversal ideas
. This is very important, if you don't know friends, I hope you can remember this.
In-order traversal¶
Related questions 94.binary-tree-inorder-traversal
The order of Inorder traversal is left-root-right
, and the root node is not output first, which is a little complicated.
-
The root node is pushed into the stack
-
Determine whether there is a left node, if there is, then push the stack until the leaf node
At this time, all the left and root nodes are saved in the stack.
- Pop out of the stack, judge whether there is a right node, then push to the stack, and continue to execute 2
It is worth noting that the result of traversing a binary search tree (BST) in order is an ordered array
. Some problems can be simplified by using this property.
For example
Post-order traversal¶
Related questions 145.binary-tree-postorder-traversal
The order of post-order traversal is left-right-root
This is a bit difficult, or it won't be difficult for leetcode.
In fact, this also belongs to the root node and does not output first, and the root node is the last output. Here is a tricky approach, Is to record the current node status, if:
-
The current node is a leaf node or
-
The left and right subtrees of the current node have been traversed, then the stack can be popped.
For 1. The current node is a leaf node
, this is a better judgment, as long as it is judged whether left and rigt are both null at the same time.
For 2. The left and right subtrees of the current node have been traversed
, only one variable record is needed. In the worst case, we record the access status of each node, and the space complexity is O(n) But think about it carefully, we use the structure of the stack, starting from the leaf node, we record a current element that is popped from the stack, and the space complexity is O(1). Please see the link above for details.
Level Traversal¶
The key point of level traversal is how to record whether each level is traversed. We can use a flag to indicate the end of the current level.
specific methods:
-
The root node enters the queue and merges into the queue with a special flag, here is null
-
Dequeue
-
Determine whether it is null, if it is, it means that the layer has ended. We again judge whether the current queue is empty, if it is not empty, continue to enqueue a null, otherwise it means that the traversal has been completed, and we don’t need to do anything.
-
If it is not null, it means that this layer is not finished yet, and put its left and right subtrees into the queue in turn.
related question:
Two-color notation¶
We know that among the garbage collection algorithms, there is an algorithm called three-color notation. which is:
-Use white to indicate not yet visited -Gray means that the child node has not been fully accessed -Black means all child nodes are visited
Then we can imitate its idea and use two-color notation to unify the tree traversals.
The core ideas are as follows:
-Use colors to mark the status of nodes, new nodes are white, and visited nodes are gray. -If the node encountered is white, mark it as gray, and then put its right child node, self, and left child node onto the stack in turn. -If the encountered node is gray, the value of the node is output.
The in-order traversal achieved using this method is as follows:
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
WHITE, GRAY = 0, 1
res = []
stack = [(WHITE, root)]
while stack:
color, node = stack.pop()
if node is None: continue
if color == WHITE:
stack.append((WHITE, node.right))
stack.append((GRAY, node))
stack.append((WHITE, node.left))
else:
res.append(node.val)
return res
It can be seen that the realization of WHITE means the first entry process in the recursion, and Gray means the process of returning from the leaf node in the recursion. Therefore, this iterative way of writing is closer to the essence of recursive writing.
If you want to achieve pre-order and post-order traversal, you only need to adjust the stacking order of the left and right child nodes. It can be seen that the use of three-color notation is similar to the recursive form, so it is easy to remember and write, but the disadvantage is that it uses additional memory space. However, this extra space is linear, and the impact is not significant.
Although recursion is also an extra linear time, the stack overhead of recursion is still more expensive than a 0,1 variable. In other words, the constant terms of space complexity are different, and in some cases the difference is quite obvious.
Morris Traversal¶
We can use a method called Morris traversal, which neither uses recursion nor the stack. Thus, the process is completed in the \(O(1)\) space.
def MorrisTraversal(root):
curr = root
while curr:
# If left child is null, print the
# current node data. And, update
# the current pointer to right child.
if curr.left is None:
print(curr.data, end= "")
curr = curr.right
else:
# Find the inorder predecessor
prev = curr.left
while prev.right is not None and prev.right is not curr:
prev = prev.right
# If the right child of inorder
# predecessor already points to
# the current node, update the
# current with it's right child
if prev.right is curr:
prev.right = None
curr = curr.right
# else If right child doesn't point
# to the current node, then print this
# node's data and update the right child
# pointer with the current node and update
# the current with it's left child
else:
print (curr.data, end=" ")
prev.right = curr
curr = curr.left
Reference: what-is-morris-traversal
Related topics¶
- 98. Validate Binary Search Tree
- 102. Binary Tree Level Order Traversal
- 103. Binary Tree Zigzag Level Order Traversal
- 104. Maximum Depth of Binary Tree
- 107. Binary Tree Level Order Traversal II
- 110. Balanced Binary Tree
- 124. Binary Tree Maximum Path Sum
- 236. Lowest Common Ancestor of a Binary Tree
- 701. Insert into a Binary Search Tree