Visualize Binary Search Tree using Python, Tkinter and Graphviz

• Download source code - 1.1 KB

Introduction

This article is a demonstration of adding nodes to a Binary Search Tree, traversing nodes and visualizing the tree in a GUI environment using Python with Tkinter.

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
2. Left Child Address Field
3. Right Child Address 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:

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:

class Tree:
    def __init__(self):
        self.root = None
        self.nodes = ""
    def addnode(self,data):
        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))
        self.addedge(root,dot)
        dot.render("tree",format="png")
    def addedge(self,node,dot):
        if node.left:
            dot.node(str(node.left.data))
            dot.edge(str(node.data),str(node.left.data))
            self.addedge(node.left,dot)
        if node.right:
            dot.node(str(node.right.data))
            dot.edge(str(node.data),str(node.right.data))
            self.addedge(node.right,dot)

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:

def add():
    tree.addnode(txtvalue.get())
    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)

    btnadd = Button(root,text="Add",command=add)
    btnadd.place(x=50,y=100,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.

Points of Interest

I hope readers find this article and its concept useful.

History

• 21^st February, 2024: Initial version