Hadron DaVinci

Build Binary Tree from Postorder

07 Nov 2020 - Hadron DaVinci

Problem
Build a binary tree from a list that represents the postordering 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 postordering 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 postorder: ['~', '~', 2, '~', '~', 7, '~', '~', 4, 5, 3, '~', '~', '~', 4, 5, 6]

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

Truths

1. Since this is a postorder, nodes are arranged in this fashion: (node.left, node.right, node)
2. Since this is a postorder, the last node in given input is the root node
3. It is advantageous to parse this input from right to left instead of left to right b/c:
   • the first node we would encounter is the root node which means that we could
     reuse code we wrote for parsing a preordered node list.
4. Parsing from right to left is the same as reversing input and parsing left to right

   Method

   TC: O(n)
   SC: O(n)
   
   This method is exactly the same as building a binary tree with a preorder except:

   • The node_list input is reversed, so the first node accessed is still the root node.
   • Since the node_list was reversed, the code passes by
     (and assigns) the right node before the left node.

Note: it is possible to parse the input without reversing the node_list but that makes the code more complex
and increases spatial complexity since it has to hold on to intermediate nodes before assigning them to parents.

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="~"):
        """
        Since root node is at the end of the input node_list,
        The list is reversed so this code still starts at the root node
        :param node_list: input of node information
        :param null_char: represents end of path
        """
        self.null_char = null_char
        self.node_list = node_list[::-1]
        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 with postorder input by appending the next node.
        Since the input was reversed, code passes by right node before left 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.right = self.insert_next_node()
            temp_node.left = 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__":
    postorder_node_data = ['~', '~', 2, '~', '~', 7, '~', '~', 4, 5, 3, '~', '~', '~', 4, 5, 6]
    bt = BinaryTree(postorder_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