Tree Traversal
The function is handed a log book from the parameter. Now it needs to travel down this tree and log its visits in a top-down (root to leaf) fashion.
Without using recursion or corecursion specifically, one may traverse a tree by starting at the root node, placing its child nodes in a data structure, then iterating by removing node after node from the data structure while placing each removed node's children back into that data structure.[b] If the data structure is a stack (LIFO), this yields depth-first traversal, and if the data structure is a queue (FIFO), this yields breadth-first traversal. -- Wikipedia
Preorder Traversal (LC.144)
Given a binary tree, return the preorder traversal of its nodes' values.
Analysis
Traverse - traverse the entire tree and add nodes in a certain order. preorder will add root.val in the beginning, inorder will add root.val in the middle, and postorder will add root.val in the end.
D&C - the boss breaks down his task into the same subproblems and assign his employees to do it then report to the boss when they are done. *One major difference b/w traverse and D&C is that D&C must have a return value (the report to the boss).
Iteratively - use an explicit stack and be careful with the ordering. Iterative DFS has the opposite ordering as the recursive DFS.
Traverse
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> visitLog = new ArrayList<>();
preOrderHelper(root, visitLog);
return visitLog;
}
private void preOrderHelper(TreeNode root, ArrayList<Integer> visitLog) {
// base case
if (root == null) {
return;
}
// log
visitLog.add(root.val);
// visit
preOrderHelper(root.left, visitLog);
preOrderHelper(root.right, visitLog);
}func preorderTraversal(root *TreeNode) []int {
log := []int{}
if root == nil {
return log
}
var preorderHelper func(node *TreeNode)
preorderHelper = func(node *TreeNode) {
// base case
if node == nil {
return
}
// preorder traversal
log = append(log, node.Val)
preorderHelper(node.Left)
preorderHelper(node.Right)
}
preorderHelper(root)
return log
}class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
log = []
self.preorderHelper(root, log)
return log
def preorderHelper(self, root: TreeNode, log: List[int]) -> None:
if root is None:
return
log.append(root.val)
self.preorderHelper(root.left, log)
self.preorderHelper(root.right, log)D&C
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
// base case
if (root == null) {
return result;
}
// divide
List<Integer> leftSubtree = preorderTraversal(root.left);
List<Integer> rightSubtree = preorderTraversal(root.right);
// conquer
result.add(root.val);
result.addAll(leftSubtree);
result.addAll(rightSubtree);
return result;
}def preorderTraversal(self, root: TreeNode) -> List[int]:
# base
if root is None:
return []
# divide
left_tree = self.preorderTraversal(root.left)
right_tree = self.preorderTraversal(root.right)
# merge
return [root.val] + left_tree + right_treeIteratively
Dump children nodes to a data structure. This is like a regular DFS (w/ opposite ordering). Pretty easy to understand.
public ArrayList<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> visitLog = new ArrayList<>();
if (root == null) {
return visitLog;
}
// init stack
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
// preorder search
while (!stack.isEmpty()) {
TreeNode current = stack.pop();
visitLog.add(current.val);
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
return visitLog;
}def preorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
# iterative
stack: List[TreeNode] = []
log: List[int] = []
stack.append(root)
while len(stack) > 0:
cur = stack.pop()
log.append(cur.val)
if cur.right is not None:
stack.append(cur.right)
if cur.left is not None:
stack.append(cur.left)
return log N-ary Tree Preorder Traversal (LI.1526)
public List<Integer> preorder(UndirectedGraphNode root) {
List<Integer> log = new ArrayList<>();
if (root == null) {
return log;
}
// iterative
Stack<UndirectedGraphNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
UndirectedGraphNode cur = stack.pop();
log.add(cur.label);
for (int i = cur.neighbors.size() - 1; i >= 0; i--) {
stack.push(cur.neighbors.get(i));
}
}
return log;
}Inorder Traversal (LC.94)
Given a binary tree, return the inorder traversal of its nodes' values.
Traverse
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> visitLog = new ArrayList<>();
inOrderHelper(root, visitLog);
return visitLog;
}
private void inOrderHelper(TreeNode root, ArrayList<Integer> visitLog) {
// base case
if (root == null) {
return;
}
// visit left
inOrderHelper(root.left, visitLog);
// log
visitLog.add(root.val);
// visit right
inOrderHelper(root.right, visitLog);
}class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
log = []
self.inorderHelper(root, log)
return log
def inorderHelper(self, root: TreeNode, log: List[int]) -> None:
if root is None:
return
self.inorderHelper(root.left, log)
log.append(root.val)
self.inorderHelper(root.right, log)D&C
Trace this one. It makes sense to go down all the way to the left, print and backtrack, print then go right, then backtrack.
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
// base case
if (root == null) {
return result;
}
// divide
List<Integer> leftSubtree = inorderTraversal(root.left);
List<Integer> rightSubtree = inorderTraversal(root.right);
// conquer
result.addAll(leftSubtree);
result.add(root.val);
result.addAll(rightSubtree);
return result;
} def inorderTraversal(self, root: TreeNode) -> List[int]:
# base
if root is None:
return []
# divide
left_tree = self.inorderTraversal(root.left)
right_tree = self.inorderTraversal(root.right)
# merge
return left_tree + [root.val] + right_tree Iteratively
The else statement kinda works as an iterative backtracking. We want to stop the search when the current pointer is at bottom right of the binary tree and nothing to backtrack to.
public ArrayList<Integer> inorderTraversal(TreeNode root) {
ArrayList<Integer> visitLog = new ArrayList<>();
if (root == null) { return visitLog; }
// init stack
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
// inorder search
while (!stack.isEmpty() || current != null) {
// left child first
if (current != null) {
stack.push(current);
current = current.left;
} else {
// log inorder
current = stack.pop();
visitLog.add(current.val);
// right at last
current = current.right;
}
}
return visitLog;
}It can be hard to implement the iterative version of in-order traversal after pre-order traversal. There are 2 distinctions to help clarifying the approach.
When to backtrack?
Should be coupled with stack frame being removed
Where does the last iteration stop?
Same place with each subtree (the traversal is recursive in nature)
Going through the tree will help visualize the algorithmic movement. But going through a base case will help implement the stop condition correctly.
class Solution:
# dump then pop
# vs keep dumping then pop
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
cur = root
stack = deque()
log = []
# where does this while loop stop?
# most right null leaf
while len(stack) > 0 or cur is not None:
# keep dumping
if cur is not None:
stack.append(cur)
cur = cur.left
else:
# pop if cur is None
if len(stack) > 0:
cur = stack.pop() # backtracking
log.append(cur.val)
cur = cur.right
return logPostorder Traversal (LC.145)
Given a binary tree, return the postorder traversal of its nodes' values.
Traverse
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
postorderTraverse(root, result);
return result;
}
private void postorderTraverse(TreeNode root, List<Integer> result) {
// base case
if (root == null)
return;
postorderTraverse(root.left, result);
postorderTraverse(root.right, result);
result.add(root.val);
}class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
log = []
self.postorderHelper(root, log)
return log
def postorderHelper(self, root: TreeNode, log: List[int]) -> None:
if root is None:
return
self.postorderHelper(root.left, log)
self.postorderHelper(root.right, log)
log.append(root.val)D&C
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
// base case
if (root == null) {
return result;
}
// divide
List<Integer> leftSubtree = postorderTraversal(root.left);
List<Integer> rightSubtree = postorderTraversal(root.right);
// conquer
result.addAll(leftSubtree);
result.addAll(rightSubtree);
result.add(root.val);
return result;
} def postorderTraversal(self, root: TreeNode) -> List[int]:
# base
if root is None:
return []
# divide
left_tree = self.postorderTraversal(root.left)
right_tree = self.postorderTraversal(root.right)
# merge
return left_tree + right_tree + [root.val] Iteratively
the key is to understand the use of lastVisit and peek
peek is for going right first before root
what about lastVisit? make sure you don't step down on the right path again
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
if (root == null)
return result;
Stack<TreeNode> stack = new Stack<>();
TreeNode visit = root, lastVisit = null, peek = null;
while (visit != null || !stack.isEmpty()) {
if (visit != null) {
stack.push(visit);
visit = visit.left;
} else {
peek = stack.peek();
if (peek.right != null && lastVisit != peek.right) {
visit = peek.right;
} else {
result.add(peek.val);
lastVisit = stack.pop();
}
}
}
return result;
}Time & Space Complexity
duh we need to visit all the nodes so time will be O(V). The stack space is proportional to the height of the tree. Note: the height of tree is not necessarily logn, the worst case can be n, a linear tree. So we have O(h) where a balanced tree can be O(logn) and a linear tree can be O(n).
References
Wikipedia Tree Traversal
ʕ； •`ᴥ•´ʔ
Last updated