How to Implement a Tree in Python

How to implement a binary search tree in Python?

Here is a quick example of a binary insert:

class Node:
def __init__(self, val):
self.l_child = None
self.r_child = None
self.data = val

def binary_insert(root, node):
if root is None:
root = node
else:
if root.data > node.data:
if root.l_child is None:
root.l_child = node
else:
binary_insert(root.l_child, node)
else:
if root.r_child is None:
root.r_child = node
else:
binary_insert(root.r_child, node)

def in_order_print(root):
if not root:
return
in_order_print(root.l_child)
print root.data
in_order_print(root.r_child)

def pre_order_print(root):
if not root:
return
print root.data
pre_order_print(root.l_child)
pre_order_print(root.r_child)

r = Node(3)
binary_insert(r, Node(7))
binary_insert(r, Node(1))
binary_insert(r, Node(5))

     3
/ \
1 7
/
5

print "in order:"
in_order_print(r)

print "pre order"
pre_order_print(r)

in order:
1
3
5
7
pre order
3
1
7
5

Implementation of a Binary Search Tree in Python with BST Class and Node Class

The issues:

  • root should be self.root.

  • == is not an assignment. It should be =

  • you should exit the function after setting the root, and not continue with the rest of the function:

    if self.root is None:
    self.root = Node(value) # Assign!
    return # don't continue
  • The conditions in the if statements that you have in the while loop, should be testing the opposite. When you don't have a left child, then you should attach a new node there, not when there is already a node there:

      if(value < current.value):
    if not current.left: # Opposite condition
    current.left = Node(value)
    break
    current = current.left
    else:
    if not current.right: # Opposite condition
    current.right = Node(value)
    break
    current = current.right

All code:

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

class BST:
def __init__(self):
self.root = None

def insert(self, value):
if self.root is None: # root is an attribute, not a variable
self.root = Node(value) # Assign!
return # Don't continue

current = self.root
while(True):
if(value < current.value):
if not current.left: # Opposite condition
current.left = Node(value)
break
current = current.left
else:
if not current.right: # Opposite condition
current.right = Node(value)
break
current = current.right

if __name__ == '__main__':
tree = BST()
tree.insert(10)
tree.insert(5)
tree.insert(6)
print("Tree Inserted Successfully")
print(tree.root.left.right.value) # Should output: 6

Trying to implement tree and calculate it's height in python

There are these issues in your code:

  • children is defined as a class attribute, so whenever you look at j.children, it is always the same list that is shared by all nodes. Your class should not have any class attributes. For the data and parent attributes, you have also defined them as instance attributes, so there the problem does not occur. Fix as follows:

    class node:
    # removed class attributes

    def __init__(self, parent, data):
    self.data=data
    self.parent=parent
    self.children = [] # added
  • The condition p.data==c.parent is never true, because it compares a string with a number. To avoid this, first convert the input list to a list of numbers at the start of your program:

    l = list(map(int, input().split()))
  • enumerate will return a tuple with first the index, and then the value. You unpacked that tuple in the opposite way, and so the tree could never be built correctly. Change:

    for n, i in enumerate(l):

    to:

    for i, n in enumerate(l):
  • The height for a leaf node should be 0, since the formal definition of height is the length of the longest path from the root to a leaf. The length of a path is expressed in the number of edges. As there is no edge in a tree with just one node, the height should be 0 for such a node.

    So:

    if len(Tree.root.children)==0:
    return 0 # not 1
  • cal_height goes wrong when it sets a new root with this statement:

    t.set_root(child.parent, child.data)

    Here you make a node that has no children! So even if child had children, they will not be considered. The recursive call to cal_height will not bring anything useful now: it will always return 1.

  • cal_height shouldn't need to create new tree and node instances. You already have the tree, and this function should not need to change anything to it. It should be a read-only operation.

    This function needs to be completely reviewed. I propose this:

    def cal_height(Tree):

    def height(node):
    if not node:
    return -1
    return 1 + max(map(height, node.children), default=-1)

    return height(Tree.root)

With these changes it will work.

Without tree

You actually don't need to create a tree or nodes at all. This can be done with a mere list that logs the depth of each node. If from each node (index) you follow the parent references until you encounter -1, then you really walk up the tree and know the depth of the original node you started from. By registering the depths for all the nodes along the way you can avoid traveling the same subpaths over and over again. The node that has the greatest depth, has a depth that is equal to the height of the tree.

Spoiler solution:

def get_height(parents):
depths = [-1] * len(parents)

def get_depth(i):
if i == -1:
return -1
if depths[i] == -1:
depths[i] = 1 + get_depth(parents[i])
return depths[i]

for i in range(len(parents)):
get_depth(i)
return max(depths)

n = input()
parents = list(map(int,input().split()))
height = get_height(parents)
print(height)

Decision Binary Tree implementation in Python with recursive function

The main problem is here:

abd.insert_left(cons_tree_sub(tag-1, subList1))

Because abd.insert_left expects a value as argument, but you pass it a node instance (as this is what cons_tree_sub returns).

So do:

abd.left = cons_tree_sub(tag-1, subList1)

...or create a setter, or alter insert_left so that it can also deal with node instances.

I would change the node constructor so it can optionally take arguments for left and right children:

def __init__(self, value, left=None, right=None):
self.value= value
self.left = left
self.right = right

I would also use a more atomic base case for the recursion, and make use of math.log2.

Then you could reduce code and write cons_tree as follows:

def cons_tree(lst):
size = len(lst)
if size == 1:
return BinaryTree(lst[0])
mid = size//2
return BinaryTree(int(math.log2(size)), cons_tree(lst[:mid]), cons_tree(lst[mid:]))

Binary Tree/Search Tree

Yes, there are these two ways.

First of all, in the 1-class approach, that class is really the Node class (possibly named differently) of the 2-class approach. True, all the methods are then on the Node class, but that could also have been the case in the 2-class approach, where the Tree class would defer much of the work by calling methods on the Node class. So what the 1-class approach is really missing, is the Tree class. The name of the class can obscure this observation, but it is better to see it that way, even when the methods to work with the tree are on the Node class.

The difference becomes apparent when you need to represent an empty tree. With the 1-class approach you would have to set your main variable to None. But that None is a different concept than a tree without nodes. Because on an object that represents an empty tree one can still call methods to add nodes again. You cannot call methods on None. It also means that the caller needs to be aware when to change its own variable to None or to a Node instance, depending on whether the tree happened to be (or become) empty.

With the 2-class system this management is taken out of the hands of the caller, and managed inside the Tree instance. The caller will always use the single reference to that instance, independent on whether the tree is empty or not.

Examples

1. Creating an empty tree

1-class approach:

root = None

2-class approach:

tree = Tree()

2. Adding a first value to an empty tree

1-class approach

# Cannot use an insert method, as there is no instance yet
root = new Node(1) # Must get the value for the root

2-class approach

tree.insert(1)  # No need to be aware of a changing root

As the 1-class approach needs to get the value of the root in this case, you often see that with this approach, the root is always captured like that, even when the tree was not empty. In that case the value of the caller's root variable will not really change.

3. Deleting the last value from a tree

root = root.delete(1)  # Must get the new value for the root; could be None!  

2-class approach

tree.delete(1)  # No need to be aware of a changing root

Even though the deletion might in general not lead to an empty tree, in the 1-class approach the caller must take that possibility into account and always assign to its own root reference, as it might become None.

Variants for 1-class systems

1. A None value

Sometimes you see approaches where an empty tree is represented by a Node instance that has a None-value, so to indicate this is not really data. Then when the first value is added to the tree, that node's value is updated to that value. In this way, the caller does no longer have to manage the root: it will always be a reference to the same Node instance, which sometimes can have a None value so to indicate the tree is actually empty.

The code for the caller to work with this 1-class variant, would become the same as the 2-class approach.

This is bad practice. In some cases you may want a tree to be able to have a None-value as data, and then you cannot make a tree with such a value, as it will be mistaken for a dummy node that represents an empty tree

2. Sentinel node

This is a variant to the above. Here the dummy node is always there. The empty tree is represented by a single node instance. When the first value is inserted into the tree, this dummy node's value is never updated, but the insertion happens to its left member. So the dummy node never plays a role for holding data, but is just the container that maintains the real root of the tree in its left member. This really means that the dummy node is the parallel of what the Tree instance is in the 2-class approach. Instead of having a proper root member, it has a left member for that role, and it has no use for its right member.

How native data structures are implemented

The 2-class approach is more like how native data types work. For instance, take the standard list in Python. An empty list is represented by [], not by None. There is a clear distinction between [] and None. Once you have the list reference (like lst = []), that reference never changes. You an append and delete, but you never have to assign to lst itself.

How to create a Binary Tree in Python?

Function t just creates a binary tree. If you want to print a tree you need to traverse it and print it. Depending on the way you want to print a tree, there are different traversal techniques, the popular of which are Inorder, Preorder and Postorder. Check this wiki link for tree traversal methods.

Your code has to be extended to do the required tree traversal. Sample is below:

# Binary tree node
class node:

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

# Function to create a new
# Binary node
def newNode(data):
return node(data)

def t():
root=newNode("A")
root.left = newNode("B")
root.right = newNode("C")
root.left.left = newNode("D")
root.left.right = newNode("G")
root.right.right = newNode("E")
root.right.right.left = newNode("F")
return root

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

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

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

root = t()

print ("In Order")
in_order(root)
print ("Pre Order")
pre_order(root)
print ("Post Order")
post_order(root)

Output:

In Order
D
B
G
A
C
F
E
Pre Order
A
B
D
G
C
E
F
Post Order
D
G
B
F
E
C
A


Related Topics



Leave a reply



Submit