• Skip to primary navigation
  • Skip to main content
  • Skip to primary sidebar
PythonForBeginners.com

PythonForBeginners.com

Learn By Example

  • Home
  • Learn Python
    • Python Tutorial
  • Categories
    • Basics
    • Lists
    • Dictionary
    • Code Snippets
    • Comments
    • Modules
    • API
    • Beautiful Soup
    • Cheatsheet
    • Games
    • Loops
  • Python Courses
    • Python 3 For Beginners
You are here: Home / Data Structures / Tree Data Structure in Python

Tree Data Structure in Python

Author: Aditya Raj
Last Updated: September 8, 2021

Python is a very rich language in terms of features and data structures. It has a lot of inbuilt data structures like python dictionary, list, tuple, set, frozenset, etc. Apart from that, we can also create our own custom data structures using Classes. In this article, we will learn about Binary tree data structure in Python and will try to implement it using an example.

Table of Contents
  1. What is a Tree Data Structure in Python?
  2. Parts of a Tree Data structure
  3. What is a Binary Tree?
  4. Conclusion

What is a Tree Data Structure in Python?

A Tree is a Data structure in which data items are connected using references in a hierarchical manner. Each Tree consists of a root node from which we can access each element of the tree. Starting from the root node, each node contains zero or more nodes connected to it as children. A simple binary tree can be depicted as seen in the following figure.

Tree Data Structure

Parts of a Tree Data structure

A tree consists of a root node, leaf nodes and internal nodes. Each node is connected to its chile via a reference, which is called an edge. 

Root Node: Root node is the topmost node of a tree. It is always the first node created while creating the tree and we can access each element of the tree starting from the root node. In the above example, the node containing element 50 is the root node.

Parent Node: The parent of any node is the node which references the current node. In the above example, 50 is the parent of 20 and 45, 20 is parent of 11, 46 and 15. Similarly 45 is the parent of 30 and 78.

Child Node: Child nodes of a parent node are the nodes at which the parent node is pointing using the references. In the example above, 20 and 45 are children of 50. The nodes 11, 46, and 15 are children of 20 and 30 and 78 are children of 45.

Edge: The reference through which a parent node is connected to a child node is called an edge. In the above example, each arrow that connects any two nodes is an edge.

Leaf Node: These are those nodes in the tree which have no children. In the above example, 11, 46, 15, 30, and 78 are leaf nodes.

Internal Nodes: Internal Nodes are the nodes which have at least one child. In the above example, 50, 20 and 45 are internal nodes.

What is a Binary Tree?

A binary tree is a tree data structure in which each node can have a maximum of 2 children.  It means that each node in a binary tree can have either one, or two or no children. Each node in a binary tree contains data and references to its children. Both the children are named as left child and the right child according to their position. The structure of a node in a binary tree is shown in the following figure.

Node of a Binary Tree in Python
Node of a Binary Tree

We can define a node of the structure shown above in python using classes as follows.

class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.leftChild = None
    self.rightChild=None

Here the constructor of the node takes the data value as input, creates an object of BinaryTreeNode type and initializes the data field equal to given input and initializes the references to the children to None. The children can be assigned to the nodes later. An example of a binary tree is shown in the figure below.

 Binary Tree in Python
Binary Tree Data Structure

We can implement the above binary tree in python as follows.

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None


node1 = BinaryTreeNode(50)
node2 = BinaryTreeNode(20)
node3 = BinaryTreeNode(45)
node4 = BinaryTreeNode(11)
node5 = BinaryTreeNode(15)
node6 = BinaryTreeNode(30)
node7 = BinaryTreeNode(78)

node1.leftChild = node2
node1.rightChild = node3
node2.leftChild = node4
node2.rightChild = node5
node3.leftChild = node6
node3.rightChild = node7

print("Root Node is:")
print(node1.data)

print("left child of the node is:")
print(node1.leftChild.data)

print("right child of the node is:")
print(node1.rightChild.data)

print("Node is:")
print(node2.data)

print("left child of the node is:")
print(node2.leftChild.data)

print("right child of the node is:")
print(node2.rightChild.data)

print("Node is:")
print(node3.data)

print("left child of the node is:")
print(node3.leftChild.data)

print("right child of the node is:")
print(node3.rightChild.data)

print("Node is:")
print(node4.data)

print("left child of the node is:")
print(node4.leftChild)

print("right child of the node is:")
print(node4.rightChild)

print("Node is:")
print(node5.data)

print("left child of the node is:")
print(node5.leftChild)

print("right child of the node is:")
print(node5.rightChild)

print("Node is:")
print(node6.data)

print("left child of the node is:")
print(node6.leftChild)

print("right child of the node is:")
print(node6.rightChild)

print("Node is:")
print(node7.data)

print("left child of the node is:")
print(node7.leftChild)

print("right child of the node is:")
print(node7.rightChild)

Output:

Root Node is:
50
left child of the node is:
20
right child of the node is:
45
Node is:
20
left child of the node is:
11
right child of the node is:
15
Node is:
45
left child of the node is:
30
right child of the node is:
78
Node is:
11
left child of the node is:
None
right child of the node is:
None
Node is:
15
left child of the node is:
None
right child of the node is:
None
Node is:
30
left child of the node is:
None
right child of the node is:
None
Node is:
78
left child of the node is:
None
right child of the node is:
None

Conclusion

In this article, we have discussed tree data structure and binary tree data structure in Python. To learn more about data structures in Python, you can read this article on Linked list in python.

Related

Recommended Python Training

Course: Python 3 For Beginners

Over 15 hours of video content with guided instruction for beginners. Learn how to create real world applications and master the basics.

Enroll Now

Filed Under: Data Structures Author: Aditya Raj

More Python Topics

API Argv Basics Beautiful Soup bitly Cheatsheet Code Code Snippets Command Line Comments Concatenation crawler Data Structures Data Types deque Development Dictionary Dictionary Data Structure In Python Error Handling Exceptions Filehandling Files Functions Games GUI Json Lists Loops Mechanzie Modules Modules In Python Mysql OS pip Python Python On The Web Python Strings Queue Requests Scraping Scripts Split Strings System & OS urllib2

Primary Sidebar

Menu

  • Basics
  • Cheatsheet
  • Code Snippets
  • Development
  • Dictionary
  • Error Handling
  • Lists
  • Loops
  • Modules
  • Scripts
  • Strings
  • System & OS
  • Web

Get Our Free Guide To Learning Python

Most Popular Content

  • Reading and Writing Files in Python
  • Python Dictionary โ€“ How To Create Dictionaries In Python
  • How to use Split in Python
  • Python String Concatenation and Formatting
  • List Comprehensions in Python
  • How to Use sys.argv in Python?
  • How to use comments in Python
  • Try and Except in Python

Recent Posts

  • Select Multiple Columns in a Pandas Dataframe
  • Select Specific Columns in Pandas Dataframe
  • Convert Epoch to Datetime in Python
  • Iterate Rows in a Pandas Dataframe
  • Split String Into Characters in Python

Copyright © 2012–2023 ยท PythonForBeginners.com

  • Home
  • Contact Us
  • Privacy Policy
  • Write For Us