Build Binary Tree from Preorder

31 Oct 2020 - Hadron DaVinci

Problem
Build a binary tree from a list that represents the preordering of nodes. Where ~ represents a null node. Then print the preorder, inorder, and postorder of tree nodes as a list.

Problem

Build a binary tree from a list that represents the preordering of nodes. Where ~ represents a null node. Then print the preorder, inorder, and postorder of tree nodes as a list.

Example

Given, node list as preorder: [6, 3, 2, '~', '~', 5, 7, '~', '~', 4, '~', '~', 5, '~', 4, '~', '~']

When converted to a binary tree we have:
The Inordering is: ['~', 2, '~', 3, '~', 7, '~', 5, '~', 4, '~', 6, '~', 5, '~', 4, '~']
The Postordering is: ['~', '~', 2, '~', '~', 7, '~', '~', 4, 5, 3, '~', '~', '~', 4, 5, 6]

Truths

Since this is a preorder, nodes are arranged in this fashion: (node, node.left, node.right)
Since this is a preorder, the first node in given input is the root node

Method

TC: O(n)
SC: O(n)

Steps:

Define Binary Tree Node

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

Define Binary Tree

class BinaryTree:
    def __init__(self, node_list: list, null_char="~"):
        self.null_char = null_char
        self.node_list = node_list
        self.build_index = 0
        self.root = self.insert_next_node()

Define Method That Builds Tree

Code recursively builds tree and returns the root node.
It can return the root node b/c the first element represents the root node.

For each node in node list, code does the following:

extracts data from the node list

creates new BinaryTreeNode

does this only if the extracted data is not the Null character, ‘~’

increments build index

that way, when the insert_next_node method is called again, it will
try to insert the next node in node list

immediately inserts the left node (And All Its Children)

inserts the right node (And All Its Children)

    def insert_next_node(self):
        """
        Builds tree by inserting the next node
        :return: temp_node
        """
        temp_node = None
        data = self.node_list[self.build_index]
        if data != self.null_char:
            temp_node = BinaryTreeNode(data=data)
        self.build_index += 1

        if temp_node:
            temp_node.left = self.insert_next_node()
            temp_node.right = self.insert_next_node()

        return temp_node

Define Method to Walk Tree In a Particular Order

This method can walk a tree in either pre, in, or post order.

    def get_ordering(self, node, order_type):
        """
        Walks binary entire binary tree in a particular order.
        Generates nodes along the way.
        :param node: node to start walking
        :param order_type: type of order used
        :return:
        """
        if node is None:
            yield None
            return

        if order_type == "pre": yield node
        yield from self.get_ordering(node.left, order_type)
        if order_type == "in": yield node
        yield from self.get_ordering(node.right, order_type)
        if order_type == "post": yield node

Define Method to Create Tree Node Lists of Various Orders
Note, if node is None, instead of appending None to the list, the character used
to represent Null ‘~’ is used.
  def create_node_list(self, order_type='pre'):
      node_list = []
      for node in self.get_ordering(self.root, order_type):
          if node is None:
              node_list.append(self.null_char)
              continue
          node_list.append(node.data)
      return node_list

Try Code:

if __name__ == "__main__":
    preorder_node_data = [6, 3, 2, '~', '~', 5, 7, '~', '~', 4, '~', '~', 5, '~', 4, '~', '~']
    bt = BinaryTree(preorder_node_data)
    print('The Preordering of tree is:', bt.create_node_list('pre'))
    print('The Inordering of tree is:', bt.create_node_list('in'))
    print('The Postordering of tree is:', bt.create_node_list('post'))

Files

method1.py