CODEWITHSUNDEEP
pythonlistbinary-tree
gra_gray
gra_gray

Reputation: 29

Traversing a binary tree using a list

code.py

class Node:
    def __init__(self,data):
        self.left = None
        self.right = None
        self.data = data

def inOrder(root):
    if root:
        inOrder(root.left)
        print (root.data)
        inOrder(root.right)

def preOrder(root):
    if root:
        print (root.data)
        preOrder(root.left)
        preOrder(root.right)

def postOrder(root):
    if root:
        postOrder(root.left)
        postOrder(root.right)
        print (root.data)

I implemented a binary tree traversal by creating Node using a class. I now want to implement binary tree traversal using only a list without using class.

Tree = [1, [2, [4,[],[]], [5,[],[]] ], [3, [], []] ]

I want to know how to implement it using this list. It is too difficult for me.

Upvotes: 0

Views: 384

Answers (1)

Abhishek J
Abhishek J

Reputation: 2584

The binary tree as list seems fairly straightforward.

The data is node/sub_arr[0], The left node is another sub array sub_arr[1] and the right node is sub_arr[2].

In the code. I merely replace node.left with tree[1], node.right with tree[2] and data with tree[0].

Tree = [1, [2, [4, [], []], [5, [], []]], [3, [], []]]


def inOrder(tree):
    if tree:
        inOrder(tree[1])  # Left
        print(tree[0])
        inOrder(tree[2])  # Right


def preOrder(tree):
    if tree:
        print(tree[0])
        preOrder(tree[1])  # Left
        preOrder(tree[2])  # Right


def postOrder(tree):
    if tree:
        postOrder(tree[1])  # Left
        postOrder(tree[2])  # Right
        print(tree[0])


print('In order')
inOrder(tree=Tree)
print('Pre Order')
preOrder(tree=Tree)
print('Post Order')
postOrder(tree=Tree)

#Output
In order
4
2
5
1
3
Pre Order
1
2
4
5
3
Post Order
4
5
2
3
1

Upvotes: 1

Related Questions