Max() function on node ; python DFS

Question

in the classic example of DFS below:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def tree_max_depth(root: Node) -> int:
    def dfs(root):
        # null node adds no depth
        if not root:
            return 0
        # num nodes in longest path of current subtree = max num nodes of its two subtrees + 1 current node
        return max(dfs(root.left), dfs(root.right)) + 1
    print(dfs(root.left))
    return dfs(root) - 1 if root else 0

# this function builds a tree from input; you don't have to modify it
# learn more about how trees are encoded in https://algo.monster/problems/serializing_tree
def build_tree(nodes, f):
    val = next(nodes)
    if val == 'x': return None
    left = build_tree(nodes, f)
    right = build_tree(nodes, f)
    return Node(f(val), left, right)

if __name__ == '__main__':
    root = build_tree(iter(input().split()), int)
    res = tree_max_depth(root)
    print(res)

How is the max function calculating the height in the line below?

return max(dfs(root.left), dfs(root.right)) + 1

The max of the heights of the subtrees, plus 1 (just as the comment says). What part of that do you have trouble with? — Scott Hunter
– Scott Hunter, Commented Jul 24, 2023 at 15:20
Thx for the resopnse scott -- what is max calculating, i understanding if I were to pass in max(3,4) it would return 4. But what does roof.left represent and how can max determine a value from it, and what is that value? — 0004
– 0004, Commented Jul 24, 2023 at 15:23
It isn't computing max of root.left; it is computing max of dfs(root.left), which is the height of the tree rooted at root.left, which is the left subtree of the tree rooted at root. — Scott Hunter
– Scott Hunter, Commented Jul 24, 2023 at 15:51

LoukasPap · Accepted Answer · 2024-08-30 16:12:16Z

2

If you understand recursion, then you can understand what the block of code does.

Let's say initial node is A. In the begining, max(dfs(root.left), dfs(root.right)) + 1 is like saying max(dfs(nodeB), dfs(nodeC)) + 1.

First, it calculates dfs(nodeB). This has root.right/left, so it doesn't return 0.
It continues to max(dfs(nodeD), dfs(nodeE)) + 1.
It goes to NodeD (root.left) which has None as root.left/right, so it returns `max(dfs(None), dfs(None))+1)=max(0,0)+1=0+1=1)
Then, it continues to dfs(nodeE) (the root.right). which have root.left/right. So it goes to dfs(nodeF). dfs(nodeF) is root has NOT root.left/right so it returns 1 (like nodeD).

So now, we have for the B node, the code max(1, 2) where '1' is from root.left (nodeD) and '2' is from nodes E and F. Then chooses the max, which is 2, and then returns 2+1 to the node A.

Node C, has height 1. So, max(3,1) is 1. So, max height is 3.

An explanation of the `root`

Each time dfs(root) is called, then a new root is set. For example, if we call dfs(nodeB) (assume nodeB is a node), then the new root is nodeB.

In the block of code:

if not root:
    return 0

the if-statement, in reality checks if the root at the moment, is None. If we substitute the code above with a root being None, it is:

if not None:
    return 0

and not None as we know results to true.

Let's take NodeD. When it's root, it does NOT have root.right & root.left (they are None). So it is calling max(dfs(None), dfs(None)) + 1 which equals to max(0, 0) + 1 because dfs(None) returns 0.

edited Aug 30, 2024 at 16:12

answered Jul 24, 2023 at 15:44

LoukasPap

1,3481 gold badge11 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

0004 Over a year ago

Thank you so much for the very helpful an comprehensive response, cannot tell you how much i appreciate. questions below: First, it calculates dfs(nodeB). This is not the root, so it doesnt return 0. Q:"Where does it indicate in the code to start at nodeB", It continues to max(dfs(nodeD), dfs(nodeE)) + 1. It goes to NodeD (root.left) which is root, so it returns 0+1=1. Q:"I thought 'root' would be NodeA' Q:"how does NodeA get assigned a value of 1"

LoukasPap Over a year ago

Answer to Q1: It does not indicate to start at nodeB. It starts from nodeA which is the first node. Then it goes max(dfs(root.left), dfs(root.right)) + 1. The root.left is nodeB and the root.right is nodeC, so it begins to calculate dfs(root.left) which is the same with dfs(nodeB).

LoukasPap Over a year ago

I've updated my answer about the root. Please ask for further explanation

Zana Mobaraki · Accepted Answer · 2023-07-30 05:37:42Z

In the given code, the 'max' function is used to determine the maximum depth (height) of the binary tree at the current node during a depth-first search (DFS) traversal.

Here's a step-by-step explanation of how it works:

The function 'tree_max_depth(root: Node) -> int' is the entry point of the program and takes the root of the binary tree as input.
The function 'dfs(root)' is a helper function that calculates the depth of the binary tree rooted at the current 'root' node using a recursive depth-first search approach.
Inside the 'dfs' function:

If the 'root' is 'None' (i.e., it represents an empty node), it means there are no nodes in the current subtree, and thus, the depth is 0. The function returns 0 in this case.

If the 'root' is not 'None', it calculates the depth of the left subtree by calling 'dfs(root.left)' and the depth of the right subtree by calling 'dfs(root.right)'.

The 'max' function is then used to find the maximum depth among the left and right subtrees. This is because the height of a binary tree is defined as the maximum depth among all its subtrees.

Adding 1 to the maximum depth of the subtrees accounts for the current node itself, so it includes the depth of the current node in the calculation.

The 'tree_max_depth' function calls 'dfs' on the root of the binary tree and returns the result after subtracting 1 from it. The subtraction is performed because the height of an empty tree (i.e., a 'None' node) is conventionally defined as -1.

To summarize, the 'max' function helps find the maximum depth among the left and right subtrees of the current node, and by adding 1 to it, it calculates the depth of the current node's subtree.

Collectives™ on Stack Overflow

Max() function on node ; python DFS

2 Answers 2

An explanation of the `root`

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

An explanation of the root

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related

An explanation of the `root`