{"id":2268,"date":"2021-11-14T15:22:16","date_gmt":"2021-11-14T20:22:16","guid":{"rendered":"https:\/\/www.alpharithms.com\/?p=2268"},"modified":"2022-06-16T15:23:48","modified_gmt":"2022-06-16T19:23:48","slug":"binary-trees-in-python","status":"publish","type":"post","link":"https:\/\/www.alpharithms.com\/binary-trees-in-python-162215\/","title":{"rendered":"Binary Trees in Python: Powerful Data Structures for Sorting & Searching"},"content":{"rendered":"

When considering data structures and algorithms one inevitably comes across binary search trees. These are a particular type of tree consisting of nodes of which each can have at most two child nodes\u2014a right and left node reference. Binary trees are efficient in a number of use cases but offer a particular advantage for searching and sorting.<\/p>\n

Even though Python is one of the most popular programming languages<\/a> it does not provide a Binary Search Tree<\/strong> (BST) class. One could arguably use the lxml<\/code> modules etree<\/code> class for such functionality\u2014but that’s not its intended purpose. Fortunately, part of Python’s popularity has stemmed from the ease by which developers can implement custom classes.<\/p>\n

Highlights<\/h2>\n

In this article, we will build a Binary Search Tree class in Python and the code required to traverse a tree in an in-order<\/strong>, pre-order<\/strong>, and post-order<\/strong> manner. We will cover the following topics in sequence:<\/p>\n

    \n
  1. Develop a Node<\/code> class to hold data and references<\/li>\n
  2. Develop an Insert<\/code> method to add data<\/li>\n
  3. Develop the three traversal functions; in-order<\/code>, pre-order<\/code>, and post-order<\/code><\/li>\n
  4. Creating and validating a Tree created using the Node<\/code> class<\/li>\n<\/ol>\n

    For our basic Binary Search Tree tutorial, we will rely solely on the Node class to create our BST. More advanced implementations stand to benefit from a formal Tree class though we will not be diving that deeply into the possibilities of a BST to warrant such complexity. Before we start coding, let’s quickly consider the essential aspects of our BST.<\/p>\n

    Introduction: The Moving Pieces<\/h2>\n

    Implementing a binary tree in Python requires some forethought into the different operations and data handling that will need to be done. At the most basic level, we need the following components:<\/p>\n

      \n
    1. Node – A structure to encapsulate our data<\/li>\n
    2. Insert – An operation to add Nodes to the Tree<\/li>\n<\/ol>\n

      That’s it! It might seem odd that there is no Tree structure mentioned here. Having a Node object which can reference a leftNode<\/code> and rightNode<\/code> gives us equivalent functionality.<\/p>\n

      Implementing a Tree object could be useful for retaining certain statistics such as overall Node count, tree height, or even tree depth. We’ll be keeping things simple for now. First, let’s create a Node class with some essential fields.<\/p>\n

      Note<\/strong>: Check out Visualgo.net’s Binary Tree Visualizer<\/a> for an interactive intro to B trees<\/em><\/p>\n

      Step 1: The Node Class<\/h2>\n
      \"node
      This illustration depicts three Node objects arranged into the most basic form of a BST\u2014a root (parent) node with references to two child nodes (a left and right)<\/figcaption><\/figure>\n

      The word\u00a0Node<\/em> is a convention used when referring to a unique item in a tree<\/strong>. In binary trees, each Node<\/code> object can have at most two references to other Nodes<\/strong>\u2014a leftNode<\/code> and a rightNode<\/code> object.\u00a0 These are considered the child Nodes. Also, each Node<\/code> needs a way to store data. Below is an implementation of a Node class for binary trees in Python:<\/p>\n

      class Node:\r\n    \r\n    def __init__(self, data):\r\n        \r\n        self.data\u00a0=\u00a0data\r\n        self.left = None\r\n        self.right = None\r\n        \r\n\r\n# Create a new Node\r\nnode_one = Node(1)<\/pre>\n
      In the example code above we’ve defined a Node<\/code> class that encapsulates an argument for data (which can be anything) and created two fields for referencing connected Nodes<\/code>. Note the references to left and right are None<\/code> by default and must be set explicitly after the creation of other Node<\/code> objects. Speaking of other Node<\/code> classes\u2014let’s consider how to start building a tree of Nodes!<\/p>\n
      Step 2: The Insert Method<\/h2>\n
      \"bst
      This image illustrates the process by which a Node with a value of 4 is inserted into an example Tree.<\/figcaption><\/figure>\n
      Our tree is going to be a nimble one\u2014only referenced via the root Node<\/code>. There will be no Tree<\/code> class object\u2014a decision taken here for simplicity. The insert<\/code> method will ensure added nodes are positioned in our resulting tree structure appropriately. We will forego any consideration for balancing our tree for now. We will approach inserting new Nodes as follows:<\/p>\n
        \n
      1. Check there is data in the new Node;<\/li>\n
      2. If that data is less than the current node’s data\n
          \n
        1. If no existing reference to a left Node, add as a new reference<\/li>\n
        2. If an existing left Node reference exists, insert into that Node<\/li>\n<\/ol>\n<\/li>\n
        3. If that data is greater than the current Node’s data\n
            \n
          1. If no existing reference to a right Node, add as a new reference<\/li>\n
          2. If an existing right Node reference exists, insert into that Node<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n
            It’s clear we will be comparing our Node’s data often. This highlights the importance that Node objects must be comparable<\/strong> to one another. This simple algorithm ensures that our Nodes form a Binary tree data structure where larger values trend towards the right and smaller values trend towards the left. Below is example code we can add to our Node class as a method to handle insertions.<\/p>\n
            def insert(self, data):\r\n\r\n    # Do nothing if no data\r\n    if self.data:\r\n\r\n        # Where data value is less than current, branch left\r\n        if data < self.data:\r\n            if self.left is None:\r\n                self.left = Node(data)\r\n            else:\r\n                self.left.insert(data)\r\n\r\n        # Where data is greater than current, branch right\r\n        elif data > self.data:\r\n            if self.right is None:\r\n                self.right = Node(data)\r\n            else:\r\n                self.right.insert(data)<\/pre>\n
            Notice we aren’t handling the case where data from one Node is equal to that of the one into which it is being inserted.\u00a0 There are several approaches to handle duplicate values:<\/p>\n
              \n
            1. Use a <= operator for either the right or left Node<\/li>\n
            2. Use a list (or running count) for duplicates per Node<\/li>\n<\/ol>\n
              Binary search trees don’t typically accommodate duplicate values as unique Nodes. Keeping a count field per Node to account for duplicates is one approach and another more performant approach would simply be to ignore duplicates altogether. How duplicates are handled comes down to one’s intended use case.<\/p>\n
              Also, note our use of the insert()<\/code> method of existing Node<\/code> objects (e.g. self.right.insert). This illustrates the recursive nature of the insert method and also demonstrates the syntactic elegance by which a BST can be organized appropriately during the initial creation and subsequent insertion of data.<\/p>\n
              Creating the Binary Search Tree<\/h2>\n
              \"binary
              This image depicts a BST created starting from a root Node with a value of 13 which dictates the order in which successive data is arranged.<\/figcaption><\/figure>\n
              Now that we have the core features of our Binary Search Tree complete we can begin working on an implementation for a set of test data. We’ll consider a very basic dataset from which we will generate our tree. Let us consider the following data:<\/p>\n
              # Node Values\r\ndata = [13, 5, 23, 4, 6, 22, 28, 3, 3, 27, 32]<\/pre>\n
              Here we have 11 values that contain two instances of 3 (a duplicate). Our final output will reflect the handling of the duplicate and the correct ordering of the data. To create a Binary Search Tree<\/strong> from our data we will first create a Node<\/code> with the value we choose for root. Then we will make use of the new Node<\/code> instance’s insert method to build our tree. This is done in the following example code;<\/p>\n
              # Create the root node from first data item\r\nroot = Node(data.pop(0))\r\n\r\n# Create and insert Node objects from remaining data\r\nfor d in data:\r\n\r\n    # Insert a new Node instance\r\n    root.insert(Node(d))<\/pre>\n
              This creates a root Node<\/code> from which our Binary Search Tree will originate and inserts new data accordingly to the tree structure. Running this will create our binary search tree\u2014but we don’t have a way to visualize it or confirm the output yet. For that, we’re going to have to discuss several ways in which a Binary Tree can be traversed.<\/p>\n
              Note<\/strong>: The placement of particular Node values depends on the order in which data is added to the tree and which Node is selected as the root. To start a tree from a specific data item\u2014one need only specify that item as the first Node to which all successive data items are inserted.<\/p>\n
              Binary Tree Traversals<\/h2>\n
              Traversing Binary Trees relies on comparisons between left and right Node values, much like the insert method. Depending on the type of traversal we specify, the order in which we consider left, right, and root differs. Below are three common types of depth-first binary tree traversal algorithms<\/strong> and the order in which they check for data at each Node.<\/p>\n
                \n
              1. In Order<\/strong>: Left, Root, Right<\/li>\n
              2. Pre-Order<\/strong>: Root, Left, Right<\/li>\n
              3. Post-Order<\/strong>: Left, Right, Root<\/li>\n<\/ol>\n
                The order in which values are checked greatly influences the order in which output is produced. The image below illustrates the process of navigation for each of these three traversal types. breadth-first and level-order traversals<\/p>\n
                \"binary
                BST data can be accessed in several orderings determined by how the nodes are traversed. The in-order, pre-order, and post-order approaches depicted here are the three most common.<\/figcaption><\/figure>\n
                Now that we have a good idea of what’s going on, we can begin implementing each traversal type. We will approach this by adding methods to our existing Node class. We’ll start with the In Order traversal type:<\/p>\n
                In-Order Traversal<\/h3>\n
                This traversal type outputs the Left Node, the Root Node, and then the Right Node. As illustrated above, if the Left Node contains data, the algorithm will recursively output data until a branch has no further depth. This can be implemented as follows:<\/p>\n
                def in_order(self, root: \"Node\") -> List[Any]:\r\n    \"\"\"\r\n    Traverse the tree in an 'in order' fashion\r\n    \"\"\"\r\n    # Create and output container\r\n    output = []\r\n\r\n    # Starting at the specified Node, \r\n    # traverse in Left, Root, Right fashion\r\n    if root:\r\n\r\n        # Check Left\r\n        output = self.in_order(root.left)\r\n\r\n        # Check Root\r\n        output.append(root.data)\r\n\r\n        # Check Right, add output to current output\r\n        output = output + self.in_order(root.right)\r\n\r\n    # Returns the list of Nodes in-order\r\n    return output<\/pre>\n
                If we call the in_order method on our tree using root.in_order(root)<\/code> then we get the following output:<\/p>\n
                [3, 4, 5, 6, 13, 22, 23, 27, 28, 32]<\/pre>\n
                Pre-Order Traversal<\/h3>\n
                This traversal type outputs the Root Node, Left Node, then Right Node. As illustrated above, the Root Node output is collected first, then the algorithm will recurse down the left then right Nodes if present. The following code implements the pre_order method:<\/p>\n
                def pre_order(self, root: \"Node\") -> List[Any]:\r\n    \"\"\"\r\n    Traverse the tree in a 'pre-order' fashion\r\n    \"\"\"\r\n    # Create and output container\r\n    output = []\r\n\r\n    #\u00a0Starting\u00a0at\u00a0the\u00a0specified\u00a0Node,\u00a0\r\n    # traverse in Root, Left, Right fashion \r\n    if root:\r\n\r\n        # Get Root Node Data\r\n        output.append(root.data)\r\n        \r\n        # Get the Left Node Data and append to current\r\n        output = output + self.pre_order(root.left)\r\n\r\n        # Get the Right node data and append to current\r\n        output = output + self.pre_order(root.right)\r\n\r\n    # Returns the list of Nodes in pre-order\r\n    return output<\/pre>\n
                If we call the pre_order<\/code> method on our tree using root.pre_order(root)<\/code> then we get the following output:<\/p>\n
                [13, 5, 4, 3, 6, 23, 22, 28, 27, 32]<\/pre>\n
                Post-Order Traversal<\/h3>\n
                This traversal type outputs the Left Node, Right Node, then Root Node. As illustrated above, the Left Node output is collected first, then the algorithm will recurse down the left then right Nodes if present, finally collecting the Root node data. The following code implements the post_order<\/code> method:<\/p>\n
                def post_order(self, root: \"Node\") -> List[Any]:\r\n    \"\"\"\r\n    Traverse the tree in a post-order fashion\r\n    \"\"\"\r\n    # Create an output container\r\n    output = []\r\n\r\n    # Starting at the specified node,\r\n    # Traverse in a left, right, root fashion\r\n    if root:\r\n\r\n        # Get left node data\r\n        output = self.post_order(root.left)\r\n\r\n        # Get right node data\r\n        output = output + self.post_order(root.right)\r\n\r\n        # Get root data\r\n        output.append(root.data)\r\n\r\n    # Returns a list of node data in pre-order\r\n    return output<\/pre>\n
                If we call the post_order method on our tree using the root.post_order(root) syntax we will get the following output:<\/p>\n
                [3, 4, 6, 5, 22, 27, 32, 28, 23, 13]<\/pre>\n
                Comparing Traversal Types<\/h2>\n
                Having noted the different traversal types it’s clear the output of a Tree is dependent on how one chooses to navigate through the data structure. For a clearer comparison, let’s consider each of our resulting output collections together:<\/p>\n
                # In Order\r\n[3, 4, 5, 6, 13, 22, 23, 27, 28, 32]\r\n\r\n# Pre Order\r\n[13, 5, 4, 3, 6, 23, 22, 28, 27, 32]\r\n\r\n# Post Order\r\n[3, 4, 6, 5, 22, 27, 32, 28, 23, 13]<\/pre>\n
                The in_order and post_order seem to produce the most similar output while the pre_order most clearly reflects the root of our tree\u2014with 13 being the first element of both input and output.<\/p>\n
                These methods can also be used to print trees as well as search them\u2014though without much style. So which way is the best? That depends on the use case and expected outcome. Generally speaking, the traversal types listed here can be beneficial when applied in the following cases:<\/p>\n