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 beself.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 continueThe 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 atj.children
, it is always the same list that is shared by all nodes. Your class should not have any class attributes. For thedata
andparent
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 = [] # addedThe 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 1cal_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 tocal_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
Looking for Recommendation on How to Convert PDF into Structured Format
In Python Can One Implement Mixin Behavior Without Using Inheritance
Is There a Function That Checks If a Character in a String Is a Letter in the Alphabet? (Swift)
Function Which Returns the Least-Squares Solution to a Linear Matrix Equation
Blocking and Non Blocking Subprocess Calls
Differencebetween List and List[:] in Python
How to Apply a Disc Shaped Mask to a Numpy Array
How to Import CSV Data into Django Models
Dead Simple Example of Using Multiprocessing Queue, Pool and Locking
How to Convert a Dictionary into a List of Tuples
Get Protocol + Host Name from Url
How to Change the Default MySQL Connection Timeout When Connecting Through Python
Multiprocessing Example Giving Attributeerror
Calling R Script from Python Using Rpy2
Data Scraping from Published Power Bi Visual
Explaining Python's '_Enter_' and '_Exit_'
Merge Pandas Dataframes Where One Value Is Between Two Others