Put into an array the deepest path of a BST (recursive)...

Question

Hello,

Im trying to put to an array the deepest path on a BST using a recursive algorithm, and im getting several difficulties... because the only thing that i get is the size of the longest path(equivalent to the height), and i cant put in the array the values regarding to the height of the BST...

Can anybody help me ???

Thanks in advance...

Sorry...i didnt expose the problem in the entire way...the only thing that i know to do this algorithm is this signatura:

//each node has 3 references : value, left and right

private int [] deepestPath(Node root){ ...}

(i can use aux methods....)

Answer 1

Try using nodes as a tool to reconstruct the deepest path

The problem you might be having is that you have no way to store the actual nodes as you traverse the tree. What you need is a way to "remember" which nodes you've visited on the way to the leaf that you deem to be the deepest.

If your BST is represented in nodes, you might want to consider storing a reference, in each child, to its parent. That way when you got to the deepest leaf, you could recursively reconstruct the path back to the root (NOTE: The path will be in reverse order). Like so:

if (isDeepest(node)) { // Once you find the deepest node...
  return reconstructPath(node); // ...reconstruct the path that took you there.
}

...

// reconstructPath is a method that takes a node (the deepest leaf) as 
// an argument and returns an array of the nodes from that node to the root.
private Array reconstructPath(Node node) {
  Array deepestPath = new Array();
  while(node.parent != node) { // Go up until you reach the root, which will be itself.
    deepestPath.add(node); // Add the node to end of the Array
    node = node.parent; // Go up one level to the parent of the node
  }
  deepestPath.reverse(); // reverse the order so it goes root->leaf
  return deepestPath;
}

There are other ways to do this if you don't want to use nodes, but this is an easy way to visualize the problem in your head.

Answer 2

With parent references

If you set up each node so that it has a reference to its parent, you can just find the deepest node and then walk back up from there to the root of the tree by tracing through the parents. That is definitely the easiest thing to do at the expense of having an extra parentNode reference variable in each node.

# Iterate through parents to trace the path in reverse.
node = deepestNode(tree)

while node.parent != None:
    node = node.parent

Without parent references

If you do not have parent references, then you can keep track of the path from the root of the tree to the "current" node as you recurse through the tree. Any time you bottom out, save that path as the "longest path so far" if the path is longer than your previous "longest path so far". Effectively that means making your call stack explicit.

Here's some Python-ish code:

# Public function. Sets up globals and then calls helper.
def deepestPath(tree):
    global longestPath, currentPath

    # Reset for a new search.
    longestPath = []
    currentPath = []

    _deepestPath(tree.root)

    return longestPath

# Helper function that does the real work.    
def _deepestPath(node):
    global longestPath, currentPath

    currentPath.append(node)

    # No children, we've bottomed out.
    if not node.left and not node.right:
        if currentPath.length > longestPath.length:
            # Save a copy of the current path.
            longestPath = list(currentPath)

    # Recurse into children.
    else:
        if node.left:  _deepestPath(node.left)
        if node.right: _deepestPath(node.right)

    currentPath.pop(node)