Can someone explain in-order traversal of binary tree recursion?

Question

I have some code to traverse a binary tree in-order recursively.

def IN_DFS(node, result=None):
    if result is None:
        result = []
    if not node:
        return result
    Solution.IN_DFS(node.left, result)

    result.append(node.val)

    Solution.IN_DFS(node.right, result)

    return result

I need some help understanding what is happening. I understand recursion, and I know how to traverse a binary tree in-order iteratively, but can't seem to see what is happening for this recursive solution.

So if 'node' is not None, we are calling the recursive function on node.left until we reach a lead node, in which case node.left is None, and we move to the next line 'result.append(node.val)'? - is this right?

Then the recursive function is called on 'node.right'?

So say we reach the first node.left leaf node, add its value to 'result' then go back up one step to its parent, add its value to 'result', then check its right child?

I don't think the above is right- anyone can help? Thanks

Arpit Chinmay · Accepted Answer · 2021-05-17 07:32:24Z

0

So if 'node' is not None, we are calling the recursive function on node.left until we reach a lead node, in which case node.left is None, and we move to the next line 'result.append(node.val)'? - is this right?- Yes, you got it right here.
So say we reach the first node.left leaf node, add its value to 'result' then go back up one step to its parent, add its value to 'result', then check its right child? No, you move to the right subtree(the right node of the current node.)

answered May 17, 2021 at 7:32

Arpit Chinmay

3426 silver badges19 bronze badges

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

13 Comments

dhuis hdiuhe Over a year ago

Thanks Arpit, that makes sense. One more thing I don't quite understand. So let's say we get to the leftmost leaf node, after processing it, we then go to the node.right, but when is the parent node itself added? Because the parent node will always have children, so in the recursion I don't see where we would add parent.node.val?

Arpit Chinmay Over a year ago

When all children have been traversed. suppose, you have a node with it's left subtree added, the program will then retrace to the parent node and traverse it's right subtree. Within the right subtree, if there is another left subtree, it will be traversed first and so on. When all of them (left and right subtrees) have been traversed the program retraces to orignal node and adds it.

Arpit Chinmay Over a year ago

you can get a deeper understanding link

dhuis hdiuhe Over a year ago

Thanks for your explanation- I did understand how the tree is traversed, where I am having difficulty is seeing how the code achieves the traversal you have mentioned. For example, I don't understand the first recursion call- let's say we get to a leaf node, this means the next node is empty, and so we hit the base case, where we will return 'result', which is empty? Then the next line of code gets called, which is to append the value of that leaf node. Where do we go from here? I understand in theory we go back to the parent then to the right child, but how does the code achieve this??

Arpit Chinmay Over a year ago

where we will return 'result', which is empty? - yes. Then the next line of code gets called, which is to append the value of that leaf node. - yes. Where do we go from here? - you go to the very next statement in the code Solution.IN_DFS(node.right, result) i.e. you pass the node to the right of the node you just appended in the result(say RIGHT). and the program again carries on as usual. It first checks the left node of RIGHT.left , then RIGHT and then RIGHT.right

|

Collectives™ on Stack Overflow

Can someone explain in-order traversal of binary tree recursion?

1 Answer 1

13 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

13 Comments

Your Answer

Sign up or log in

Post as a guest

Related