15,969,509 members
Articles / Programming Languages / Python
Article

Visualize Binary Search Tree using Python, Tkinter and Graphviz

Rate me:
21 Feb 2024CPOL3 min read 4.2K   91   5
Visualizing a Binary Search Tree using Python, Tkinter and Graphviz
With this article, I wish to demonstrate inserting and traversing nodes in a Binary Search Tree. I also wish to explain the process of visualizing graphically the relationships of nodes in a binary search tree.

Background

A tree data structure is a non-linear data structure because it does not store data sequentially. It is called as a hierarchical structure as data is arranged in multiple levels in a tree. In a tree, the topmost node is known as the root node. Each node contains some data which can be of any type and address of other node called children.

Following are some terms related to trees:

1. Root: It is the topmost node in a tree. It does not have any parent node.
2. Child: It is the descendent of some node.
3. Parent: It is a node having a sub node (child node).
4. Sibling: They are children of a common (same) parent.
5. Leaf Node: It is a node that does not have children. It is the bottom most node. It is also called as external node.
6. Internal Node: It is a node which has at least one child node.
7. Ancestor Node: It is a predecessor node on a path from the root till the current node.
8. Descendant Node: It is the immediate successor of any node.

A Binary Search Tree is a special type of tree in which each node tree can have maximum two child nodes with the restriction that the value of each node in the left subtree must be less than the value of the root node and the value of each node in the right subtree must be more than the value of the root node.

A node in a binary search tree contains three fields:

1. Data Field

Node Traversal

Nodes in a Binary Search Tree can be traversed in three ways:

(All traversal functions are recursive functions)

1. `inorder` - left-root-right
• Traverse the left subtree.
• Visit the root.
• Traverse the right subtree.
2. `preorder` - root-left-right
• Visit the root.
• Traverse the left subtree.
• Traverse the right subtree.
3. `postorder` - left-right-root
• Traverse the left subtree.
• Traverse the right subtree.
• Visit the root.

Using the Code

The application is a Tkinter based GUI application in which a user can enter data and visualize it in real time.

A node class can be used to describe a node of a Binary Search Tree as follows:

Python
```class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None```

Insertion and Traversal operations are defined in the `Tree` class as follows:

Python
```class Tree:
def __init__(self):
self.root = None
self.nodes = ""
currnode = Node(data)
if self.root is None:
self.root = currnode
else:
parent = None
ptr = self.root
while ptr is not None:
parent = ptr
if int(currnode.data) < int(ptr.data):
ptr = ptr.left
else:
ptr = ptr.right
if int(currnode.data) < int(parent.data):
parent.left = currnode
else:
parent.right = currnode
def inorder(self,root):
if root != None:
self.inorder(root.left)
self.nodes += root.data + " "
self.inorder(root.right)
def preorder(self,root):
if root != None:
self.nodes += root.data + " "
self.preorder(root.left)
self.preorder(root.right)
def postorder(self,root):
if root != None:
self.postorder(root.left)
self.postorder(root.right)
self.nodes += root.data + " "
def visualizetree(self,root):
dot = graphviz.Digraph()
dot.node(str(root.data))
dot.render("tree",format="png")
if node.left:
dot.node(str(node.left.data))
dot.edge(str(node.data),str(node.left.data))
if node.right:
dot.node(str(node.right.data))
dot.edge(str(node.data),str(node.right.data))

In the above code, the `addnode()` function adds a node to the tree at the appropriate position based on its value. The `inorder()`, `preorder()` and `postorder()` recursive functions perform the respective traversals and store the traversed node values in the nodes variable. The `visualizetree()` method performs visualization using `graphviz`. The `addedge()` function recursively draws edges from a node to its children nodes. The tree is rendered and stored as a "`png`" image in the current folder.

The following code provides the GUI environment for the application:

Python
```def add():
tree.visualizetree(tree.root)
img = ImageTk.PhotoImage(Image.open("tree.png"))
lblimage.configure(image=img)
lblimage.image = img

def inorder():
tree.inorder(tree.root)
messagebox.showinfo("Inorder",tree.nodes)
tree.nodes = ""

def preorder():
tree.preorder(tree.root)
messagebox.showinfo("Preorder",tree.nodes)
tree.nodes = ""

def postorder():
tree.postorder(tree.root)
messagebox.showinfo("Postorder",tree.nodes)
tree.nodes = ""

def showimage(event):
os.system("tree.png") if os.path.exists("tree.png") else None

if __name__ == "__main__":

tree = Tree()
root = Tk()
root.title("Binary Search Tree")
root.geometry("500x300")

lblvalue = Label(root,text="Enter data: ")
lblvalue.place(x=50,y=50,width=100)

txtvalue = Entry(root)
txtvalue.place(x=150,y=50,width=100)

btninorder = Button(root,text="Inorder",command=inorder)
btninorder.place(x=150,y=100,width=100)

btnpreorder = Button(root,text="Preorder",command=preorder)
btnpreorder.place(x=50,y=150,width=100)

btnpostorder = Button(root,text="Postorder",command=postorder)
btnpostorder.place(x=150,y=150,width=100)

lblimage = Label(root)
lblimage.bind("<Button-1>",showimage)
lblimage.place(x=300,y=50,width=150,height=150)
root.mainloop()

if os.path.exists("tree.png"):
os.remove("tree.png")
os.remove("tree")```

The above code can be used to add nodes and visualize the tree interactively. The rendered tree is displayed in a label, clicking on which opens the tree image in the default image viewer app.

History

• 21st February, 2024: Initial version

Written By
Instructor / Trainer NIIT, India
India
I am a trainer by profession. Currently I am working with iFuture Technologies(India) as a Senior Faculty. I enjoy programming as a hobby. During my career I have seen the growth and decline of many technologies, many of them being my favorites like Flash, WPF, Windows Mobile Development. Few of my current favorites are Android, Xamarin and Python, though I also like traditional and evergreen languages like PHP, C#, Visual Basic and Java.

Apart from computers, my favorite pastime is bicycling.