Binary Tree Preorder Traversal

Question

I'm just getting started with binary trees and I have this task where I have to do a preorder iterative traversal search for a given binary tree '[1,null,2,3]'.

I tried to use a new binarytree module that I found, but it didn't worked and I saw a youtube video where some guy did it recursively but I just can't figure out.

#Input = [1,null, 2,3]
# 1
#  \
#   2
#  /
# 3
#Expected output = [1,2,3]


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

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:

I'm just clueless, I wrote an algorithm but I can't turn it into actual functional code. Also I don't understand how the root: TreeNode works. Does it turn every element of the list into a TreeNode object? So far my best try had been this and it's obviously wrong in many ways.

def preorderTraversal(self, root: TreeNode) -> List[int]:
    result = []
    for i in root:
        if i =! root[0] and root.left =! None:
            root.left = i
            if root.left =! null:
                root.left.left = i
            elif root.left == null:
                root.right.left = i
            elif root.left
            result.append(i)
        elif root.right == None:
            root.right = i

        else:
            continue

Answer 1

A few points:

1. Function preorderTraversal should have no self parameter; it is not a method of a class.
2. I have modified the TreeNode class to make it more convenient to specify its children TreeNode objects.
3. Function preorderTraversal takes as an argument a TreeNode object. As I mentioned in a comment, your statement, #Input = [1,null, 2,3], is difficult to make sense of.
4. You need to keep a last in/first out (LIFO) stack of unvisited TreeNode objects to implement an iterative (rather than recursive solution). In the code below, variable nodes serves that purpose.

The code:

from typing import List

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

n3 = TreeNode(3)
n2 = TreeNode(2, left=n3)
n1 = TreeNode(1, right=n2)

def preorderTraversal(root: TreeNode) -> List[int]:
    result = []
    nodes = []
    nodes.append(root) # initial node to visit
    while len(nodes): # any nodes left top visit?
        node = nodes.pop() # get topmost element, which is the next node to visit
        result.append(node.x) # "output" its value before children are visited
        if node.right is not None:
            # show this node must be visited
            nodes.append(node.right) # push first so it is popped after node.left
        if node.left is not None:
            # show this node must be visited
            nodes.append(node.left)
    return result

print(preorderTraversal(n1))

Prints:

[1, 2, 3]

Or a more complicated tree:

        10 
      /   \ 
    8      2 
  /  \    / 
3     5  2 

n3 = TreeNode(3)
n5 = TreeNode(5)
n8 = TreeNode(8, left=n3, right=n5)
n2a = TreeNode(2)
n2b = TreeNode(2, left=n2a)
n10 = TreeNode(10, left=n8, right=n2b)

print(preorderTraversal(n10))

Prints:

[10, 8, 3, 5, 2, 2]

Answer 2

You can use the queue data structure for it.

queue = []
result = []
queue.append(root)

while queue:
    node = queue.pop()
    result.append(node.val)

    if node.left is not None:
        queue.insert(0, node.left)

    if node.right is not None:
        queue.insert(0, node.right)

return result

Answer 3

This is a problem from leetcode platform, here is my solution. Runtime: 28 ms, faster than 81.08% of Python3 online submissions for Binary Tree Preorder Traversal.

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