➜ ~

Playing Hacks and Stuffs!

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

Binary Tree Preorder Traversal

image image

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

I covered the first method of Traversing Binary Tree in this writeup you can check it out!

The rule of Preorder Traversal is this:

Let’s take an example! Consider this Binary Tree image

What we can see is that the parent node which I’ll call the key is 3 and it has two children 2 and 4

In order to traverse using the preorder method I’ll start from the current node which is 3 image

Now we move to the left tree and deal with the left subtree

In this case the left node connected to the key node is 2 and it has just one node which is the left node 1 so the list will then be [3, 2, 1]

Since we’re done with the left tree of this node we’ll move back to the key node image

Now we check for the right tree and the right node connected to the key node is 4 which also is the current node image

The current node has two children which are the left and right children

From the rule of preorder traversal after traversing the current node we should traverse the left subtree

Since the current node has just one left node that means we’ve finished traversing the left subtree then we move to the right subtree which is the right node image

So the final return value would be [3, 2, 1, 4, 6, 5]

In order to implement this using python I’ll use the generic TreeNode Class then recursively call the preorder function which would return ([node.key] + preorder(node.left) + preorder(node.right)

Here’s my solve script: link image

Leetcode Submission Script

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