CODEWITHSUNDEEP
pythonpython-3.xrecursionbinary-treebinary-search-tree
1412
1412

Reputation: 133

How to comprehend the following recursive function in binary tree?

The following is a Binary search function (a root has a left and a right child) which I don't quite comprehend. In the code it returns a list that is the longest path in the binary tree. However for the part:

return_path_left = list_longest_path(node.left)
return_path_right = list_longest_path(node.right)
if len(return_path_left) > len(return_path_right):

how can you compare two recursive call? For example, if the tree is

 1
/  \
2

list_longest_path(node.right) will surely return []. But how do you compare list_longest_path(2) with []?

Someone help will be great.

def list_longest_path(node):
    """
    List the data in a longest path of node.

    @param BinaryTree|None node: tree to list longest path of
    @rtype: list[object]

    >>> list_longest_path(None)
    []
    >>> list_longest_path(BinaryTree(5))
    [5]
    >>> b1 = BinaryTree(7)
    >>> b2 = BinaryTree(3, BinaryTree(2), None)
    >>> b3 = BinaryTree(5, b2, b1)
    >>> list_longest_path(b3)
    [5, 3, 2]
    """
    if node is None:
        return []
    else:
        return_path_left = list_longest_path(node.left)
        return_path_right = list_longest_path(node.right)
        if len(return_path_left) > len(return_path_right):
            return [node.data] + return_path_left
        else:
            return [node.data] + return_path_right

Upvotes: 2

Views: 114

Answers (2)

bterwijn
bterwijn

Reputation: 328

I've added memory_graph to your code to visualize the state of the program during execution.

import memory_graph as mg # see above link for install instructions

class Node:

    def __init__(self, value, left=None, right=None):
        self.left = left
        self.data = value
        self.right = right

    def __repr__(self):
        return str(self.value)

def list_longest_path(node):
    """
    List the data in a longest path of node.

    @param BinaryTree|None node: tree to list longest path of
    @rtype: list[object]

    >>> list_longest_path(None)
    []
    >>> list_longest_path(BinaryTree(5))
    [5]
    >>> b1 = BinaryTree(7)
    >>> b2 = BinaryTree(3, BinaryTree(2), None)
    >>> b3 = BinaryTree(5, b2, b1)
    >>> list_longest_path(b3)
    [5, 3, 2]
    """
    mg.s() # graph call stack
    if node is None:
        return []
    else:
        return_path_left = list_longest_path(node.left)
        return_path_right = list_longest_path(node.right)
        if len(return_path_left) > len(return_path_right):
            mg.s() # graph call stack
            return [node.data] + return_path_left
        else:
            mg.s() # graph call stack
            return [node.data] + return_path_right

# create some test binary tree
tree = Node(11, Node(10), Node(14, Node(13, Node(12)), Node(15)))

longest_path = list_longest_path(tree)
print(longest_path)
mg.s() # graph call stack

Assuming you don't have Adobe Acrobat or another PDF reader that locks the files it has open as your default PDF reader, you can step through the execution by pressing ENTER and see images like this that hopefully make it easier to understand the recursion:

example step

In this image the '2: list_longest_path' function on the call stack is about to return, it sees its return_path_left is longer than its return_path_right list. Thus it will return the data of its node [14] concatenated with return_path_left [12, 13] to function '1: list_longest_path' where the same thing happens. So in the end [11, 14, 12, 13] is the result.

Full disclosure: I am the developer of memory_graph.

Upvotes: 0

gnicholas
gnicholas

Reputation: 2077

list_longest_path(node.right) will surely return []. But how do you compare list_longest_path(2) with []?

When a recursive call like list_longest_path(2) is encountered, it gets pushed onto the call stack. As the call stack is a stack [and is thus last in first out] the current stack frame is halted and list_longest_path(2) is evaluated.

list_longest_path(2) is evaluated like so:

As both left and right nodes are None, return_path_left = []; return_path_right = []; So list_longest_path(2) = [2] + [] = [2]

Then the list_longest_path(2) stackframe is popped off the stack and the program resumes execution in the previous stackframe. We now have a simple value for list_longest_path(2) = [2] We then finish up the execution of this function len([2]) > len([]) so list_longest_path(1) = [1] + [2] = [1,2]

Upvotes: 1

Related Questions