Get all Paths of BinaryTree
This post continues to explore tree algorithms and specifically printing all root-to-leaf paths when given a binary tree. It will showcase the iterative pre-order depth first traversal approach to solving this problem. The general idea is to represent a path using some sort of list structure and keep track of the level of the tree at each node. The level of the tree is the index of the list to modify.
# 1
# / \
# 9 8
# / \ \
# 6 4 3
# / \ /
# 2 7 5
#
# paths: [
# [1,9,6,2],
# [1,9,6,7],
# [1,9,4],
# [1,8,3,5]
# ]Approach
As with all iterative tree traversal, we need a stack to store every node we visit such that we can backtrack each time we hit a null child. We will also need another stack to store every level we visit and backtrack as we encounter a null child. Lastly, we need two lists, one to store the current path we are constructing or updating, and the second list to store all the paths. As mentioned, the idea is to use the level of the current iteration as the index to modify in the path list. Once we hit a node with null children, we add the current path to the list of all paths. This process is repeated until all leaf nodes are visited.
public static List<String> getBinaryTreePaths(TreeNode root) {
Stack<TreeNode> parents = new Stack<TreeNode>();
Stack<Integer> levels = new Stack<Integer>();
List<Integer> path = new ArrayList<Integer>();
List<String> paths = new ArrayList<String();
TreeNode cur = root;
Integer level = 0;
while (!parents.isEmpty() || cur != null) {
if (cur != null) {
if (level >= path.size())
path.add(cur.data);
else
path.set(level, cur.data);
if (cur.left == null && cur.right == null)
paths.add(path.toString());
levels.push(level++);
parents.push(cur);
cur = cur.left;
}
else {
TreeNode parent = parents.pop();
cur = parent.right;
level = levels.pop() +1;
}
}
return paths;
}