For the below example tree, all root-to-leaf paths are:
10 –> 8 –> 3
10 –> 8 –> 5
10 –> 2 –> 2
10
8 2
3 5 2
Sol:
Algorithm:
Use a path array path[] to store current root to leaf path. Traverse from root to all leaves in top-down fashion. While traversing, store data of all nodes in current path in array path[]. When we reach a leaf node, print the path array.
10 –> 8 –> 3
10 –> 8 –> 5
10 –> 2 –> 2
10
8 2
3 5 2
Sol:
Algorithm:
Use a path array path[] to store current root to leaf path. Traverse from root to all leaves in top-down fashion. While traversing, store data of all nodes in current path in array path[]. When we reach a leaf node, print the path array.
/*Given a binary tree, print out all of its root-to-leaf
paths, one per line. Uses a recursive helper to do the work.*/
void printPaths(TreeNode T)
{
int path[1000];
printPathsRecur(T, path, 0);
}
/* Recursive helper function -- given a node, and an array containing
the path from the root node up to but not including this node,
print out all the root-leaf paths.*/
void printPathsRecur(TreeNode T, int path[], int pathLen)
{
if (node==NULL)
return;
/* append this node to the path array */
path[pathLen] = T.data;
pathLen++;
/* it's a leaf, so print the path that led to here */
if (T.left==NULL && T.right==NULL)
{
printArray(path, pathLen);
}
else
{
/* otherwise try both subtrees */
printPathsRecur(T.left, path, pathLen);
printPathsRecur(T.right, path, pathLen);
}
}
