➜ ~

Playing Hacks and Stuffs!

---

Project maintained by h4ckyou Hosted on GitHub Pages — Theme by mattgraham

Binary Tree Inorder Traversal

We are going to be given a binary tree and our goal is to return the inorder traversal of its nodes’ values

First let’s know what Traversing means:

Traversing refers to the process of visiting each node of a tree exactly once. Visiting a node generally refers to adding the node’s key to a list.

There are various ways to traverse a binary tree and return the list of visited keys

In this case I’ll deal with the Inorder Traversal method:

• Traverse the left subtree recursively inorder
• Traverse the current node
• Traverse the right subtree recursively inorder

That does not sound too good so let’s take a sample

Consider this binary tree

The key node is 3 which has two children 2 and 4 and the left and right nodes has other children

Let’s take an example on what Inorder Traversal means:

First we’ll start from the left node 2 of the key 3 and visit the left subtree first

Now we check if the left node has another left key value, in this case it does i.e the node 2 has another left node 1

We check again but in this case the node 1 does not have another node connected to it so we add that to our list and move to the current node 2 then check if it has any right subtree in this case it doesn’t

Now we move up the from the current node to the key node

At this point the value’s we’ve covered are [1, 2, 3]

Now since our current node is 3 we’ll move to the right node of the key node

We will then see that the right node has a left key value

The key value 6 does not hold any other nodes so we’ll add that to our list then move on to the current node 4, the current node value will be added to the list also

Since we are the current node we then check the right subtree which in this case is the remaining node which is 5

At this point we’ve traversed the whole tree and the return value would be:

value = [1, 2, 3, 4, 6, 5]

Now to implement this is python we can create a class object that would be used to implement a binary tree i.e

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

The remaining portion which is to implement the Inorder Traversal is going to be a recursive call to it’s inorder function returning (inorder(node.left) + [node.key] + inorder(node.right))

Note: Generally Binary Tree or Binary Search Tree deals with lots of Recursion and Classes as it's trivial

Here’s my solve script: link

Leetcode Submission Solution

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