Binary Tree Explained
A Binary Tree is a non-linear data structure that is used for searching and data organization. A binary tree is comprised of nodes. Each node being a data component, one a left child and the other the
A Binary Tree is a non-linear data structure that is used for searching and data organization. A binary tree is comprised of nodes. Each node being a data component, one a left child and the other the right child. Let us dive into the concepts related to trees and implement them into the Python programming language.
Note: Prerequisites – Make sure you have basic Python knowledge before diving into this article. It also might be a good idea to check out some linear data structures. (links are given above)
Table of Contents
Binary Trees: Introduction
A binary tree node consists of the following components:
Data
Pointer to Left Child
Pointer to Right Child
Below are some key terminologies related to a binary tree.
Node – The most elementary unit of a binary tree.
Root – The root of a binary is the topmost element. There is only one root in a binary tree.
Leaf – The leaves of a binary tree are the nodes which have no children.
Level – The level is the generation of the respective node. The root has level 0, the children of the root node is at level 1, the grandchildren of the root node is at level 2 and so on.
Parent – The parent of a node is the node that is one level upward of the node.
Child – The children of a node are the nodes that are one level downward of the node.
Applications of Binary Trees
A binary tree is a hierarchical data structure, a file system that is organized in the form of a tree. Trees can be used for efficient searching, when the elements are organized with some order. Some examples include:
The HTML/XML Document Object Model is organized in the form of a tree.
Abstract Syntax Trees and Parse Trees are constructed by a compiler as a part of compilation.
Trees are also used to efficiently index databases.
Implementing a Binary Tree
Initialize a Node Class
Let us first define the Node class.
Once we have defined the Node class, we can initialize our Binary Tree:
Traversals
Since a binary tree is a non-linear data structure, there is more than one way to traverse through the tree data. Let’s look at the various types of traversals in a binary tree, including inorder traversal, preorder traversal, and postorder traversal.
Inorder Traversal
In an inorder traversal, the left child is visited first, followed by the parent node, then followed by the right child.
Preorder Traversal
In a preorder traversal, the root node is visited first, followed by the left child, then the right child.
Postorder Traversal
In a postorder traversal, the left child is visited first, followed by the right child, then the root node.
Practice Binary Trees
Once you have understood the core concepts of a binary tree, practice the problem sets given below to strengthen and test your knowledge on trees.
Flatten Binary Tree to Linked List - LeetCode
Sum Root to Leaf Numbers - LeetCode
Symmetric Tree - LeetCode
Binary Trees - Carnegie Mellon University
Last updated