0

I'm trying to understand how this code works:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode], result: List[int] = None) -> List[int]:
        if result is None:
            result = []
        if root:
            self.inorderTraversal(root.left, result)
            result.append(root.val)
            self.inorderTraversal(root.right, result)
        return result

Suppose our tree is [5, 8, 7] (i.e., 5 is the root, its left daughter is 8 and its right daughter is 7). First, the root is given as the input. The empty results list is created. The root is not None, so the body of the if statement is executed. The first line of the if statement is supposed to call the traversal function on the left daughter of the root, i.e., on root.left. So we're back to the line "if result is None". This first if statement is skipped. For the second if statement, root.left is true, so the statement in the body of the second if statement is executed. Namely, the function calls itself for a second time, this time on the argument root.left.left. So we go back to the line "if result is None". This first if statement is skipped again. Now we get to the line "if root.left.left". But root.left.left is None, so we should not execute the code in the body of the statement and we should return "result". Where's my mistake?

Improve this question
2
  • It would be wise to work with code on your local machine where you can step through it, instead of inside a solution oracle where you can't. And no -- the root is not none at that particular time you say it is none. Commented Aug 4, 2023 at 2:05
  • I see. When the function calls itself recursively for the first time, it does so on the argument root.left. The condition "root.left" is true. Then it calls itself on the argument root.left.left, right? But in this case, root.left.left is false, so the statement of the second if loop should not get executed, and still "result" should be returned... Commented Aug 4, 2023 at 2:12

2 Answers 2

Reset to default
0

Your analysis of the process for the input [5,8,7] is correct. It just is not complete. It looks like you wonder about return result when it is still empty. But this is intended behaviour. Maybe you thought that return result would return the result to the very first caller (the code challenge framework), but that is not what happens. That result is returned to the previous caller. And that caller will then perform the append of their node's value to the same list .

Maybe it helps to visualise the call stack with boxes that are placed on top of eachother. A return only removes a box from the top of the stack, not the whole stack.

Execution flows from top of this diagram to bottom. The nested boxes represent the depth of the recursion:

┌─ root: Node 5, result: None ──────────────────────┐
│ result = []                                       │
│ self.inorderTraversal(root.left, result)          │
│  ┌─ root: Node 8, result: [] ─────────────────┐   │
│  │ self.inorderTraversal(root.left, result)   │   │
│  │  ┌─ root: None, result: [] ─────────┐      │   │
│  │  │ return result  # []              │      │   │
│  │  └──────────────────────────────────┘      │   │
│  │ result.append(root.val)  # [8]             │   │
│  │ self.inorderTraversal(root.right, result)  │   │
│  │  ┌─ root: None, result: [8] ────────┐      │   │
│  │  │ return result  # [8]             │      │   │
│  │  └──────────────────────────────────┘      │   │
│  │ return result  # [8]                       │   │
│  └────────────────────────────────────────────┘   │
│ result.append(root.val)  # [8, 5]                 │
│ self.inorderTraversal(root.right, result)         │
│  ┌─ root: Node 7, result: [8, 5] ─────────────┐   │
│  │ self.inorderTraversal(root.left, result)   │   │
│  │  ┌─ root: None, result: [8, 5] ─────┐      │   │
│  │  │ return result  # [8, 5]          │      │   │
│  │  └──────────────────────────────────┘      │   │
│  │ result.append(root.val)  # [8, 5, 7]       │   │
│  │ self.inorderTraversal(root.right, result)  │   │
│  │  ┌─ root: None, result: [8, 5, 7] ──┐      │   │
│  │  │ return result  # [8, 5, 7]       │      │   │
│  │  └──────────────────────────────────┘      │   │
│  │ return result  # [8, 5, 7]                 │   │
│  └────────────────────────────────────────────┘   │
│ return result  # [8, 5, 7]                        │
└───────────────────────────────────────────────────┘

So the inner boxes are the deepest recursive calls. Each time the result list is passed to the deeper call, which may or may not add value(s) to it. If it doesn't add values it, it just means there are no nodes there. The caller will add their own node's value to it.

Note also that return result is only needed because the top level caller expects the list as return value. All other times that a (recursive) call is made, the caller doesn't really care what is returned, because the caller already has the list: they have a reference to it with their own result name. If the recursive call added values to it, they will "have" those values, since they use the same list.

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

5 Comments

It seems my misunderstanding lies in "A return only removes a box from the top of the stack, not the whole stack." Isn't it true in general that if the last line in the definition of a function is return X, then this forces the function to exit and output the value X? I still don't understand how come that after the line return result # [] gets executed, the control passes to result.append(root.val) -- this seems to contradict what I said just above regarding return X being in the last line of the definition of a function.
Correction to my previous comment: I meant to say "if the last line in the definition of a function is return X, then this forces the function to exit and output the value X after the line return X is executed (for the first and only time)". So my point is that when the line return result is executed for the very first time, this should output the final result right away, and no code in the body of the function should be executed anymore.
A return statement doesn't output. Maybe that is the misunderstanding? It merely provides a value to the caller of the function (who may choose to ignore it), and the caller's code will proceed with execution. There is no "output" involved here. The site on which this code is executed will take the value returned by your function (it makes the top-level call) and verify it. It may decide to output it on the screen, but that is just their code, not yours.
Secondly the first time a return executes in this example scenario, it is not the "only time". No, recursion means that a stack builds up of executions of this function that each wait for the next one to return. When the last one returns, the last-but-one execution will resume execution and will eventually also execute a return, ...etc.
In the diagram I posted, you can see that at some point (when following the execution from top to bottom), there are multiple boxes "open": each represents an execution context of the same function, and each can and will eventually execute a return.
0

The function inorderTraversal takes two parameters:

  • root : representing the current node.

  • result : a list that holds the traversal outcome.

When the function is called, it first checks if the root is None, indicating the end of traversal for that subtree, and if so, returns the current state of the result list. However, if the root is not None, the function proceeds with the traversal. It initiates a recursive call to inorderTraversal for the left subtree (root.left), traversing it and adding its values to the result list. Subsequently, the function appends the value of the current node (root.val) to the result list, ensuring the correct order of values.Then, another recursive call is made, this time for the right subtree (root.right), further extending the result list. As these recursive calls unwind, the function assembles the result list step by step, yielding the values of the binary tree in the desired inorder sequence. The concern about the if result is None: check is related to initializing a fresh result list when beginning traversal from a new root, ensuring accurate accumulation of traversal results. In contrast, the misunderstanding regarding root.left.left pertains to the recursive calls being made on the immediate left and right subtrees of the current node, rather than deeper levels.

Improve this answer

1 Comment

I'm still not sure why after checking and verifying that root.left.left is None, the function doesn't return "results" (i.e., the empty list). Or, to give another view on this, I can't see a scenario in which the line "result.append(root.val)" would ever be executed because the previous line "self.inorderTraversal(root.left, result)" moves us to the very top every time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.