Books Online Courses
Free Tutorials  Go to Your University  Placement Preparation 
Latest:- Important tips to get an Off Campus Placements
0 like 0 dislike
in Examples, Exercises and Projects by (562 points)
edited by
  1. Tree
  • What is tree? 
  • Figure
  • Various terminilogies used
  1. Binary Tree
  • Its definition
  • Basic characteristics of a binary tree
  • Basic structure 
  • Its properties
  • Types of binary tree
  • Its representation
  • Advantages
  • Disadvantages

2 Answers

0 like 0 dislike
by Goeduhub's Expert (2.2k points)
edited by


What is meant by tree in data structure?

  • A tree is a non-linear data structure represented in a hierarchical manner. 
  • It contains a finite set of elements called ‘nodes’  
  • These are connected to each other using a finite set of directed lines called ‘branches’.
  • Children of same parent are called Sibling
  • Top most element of node is called the root node.  
  • The node which do not have any child is called leaf node.
  • The node that has atleast one children is called internal node.
  • Trees can also called as recursive data structure.

Various Tree terminologies 

Parent:The parent of a node is the immediate predecessor of that node.

Child:The immediate successor of a node are called child nodes. A child nodes which is placed at left side is called left child. A child which is placed at right side is called right side of a node.

Siblings:The child nodes having the same parent is called siblings.

Root:A root is a special designated node in a tree structure. It is a node which has no parent . There can be only one root node in any tree structure.

Leaf nodes(External nodes) :A leaf node which does not have any child nodes.

Internal nodes:Internal nodes which is having a parent and atleast one children are called internal nodes.

Branch and Edge:It is connecting line between two nodes . A node can have more than one edge.

Path:Each node has to be reachable from root to a unique sequence of edges is called a path. The number of edges in a path is called length of the path.

Degree of a node:The number of edges connecting of a particular node is called the degree of a node.

Degree of a tree:The maximum number of a degree of a node is called the degree of a tree.

Level of a node:The level of a node is the number of edges along the unique path between it and the root level of the root is defined as ‘zero’.If a node is at level I, then it childrens is at level I+1.This rule is common for all the nodes except the root node.

Height and depth of a tree: The maximum number of a level of a tree is called its height and depth of a tree. In other words, we can say the height of a Tree is the height of the root node or the depth of the deepest node.

Height of a Node: The height of a node is the number of edges from the node to the deepest leaf (ie. the longest path from the node to a leaf node).

Depth of a Node: The depth of a node is the number of edges from the root to the node.


Binary tree

  • In binary tree, each node can have atmost two childrens.
  • A binary tree, it is either empty or it consists of a node called ‘root node’, it having two childrens, called left subtree and the right subtree of the root


A binary tree , it is either empty or it consists of almost two childrens of a node.

Basic structures of Binary Tree

  • In this tree, codes either have 0 or 2 children.
  • We could have a node with just one child as left child or right child.
  • A node with zero childs is called leaf node.

Properties of a Binary Tree:

  • A binary tree has n number of nodes, then the number of edges are n-1.
  • For a non-empty binary tree ‘n’ is the number of nodes and ‘e’ is number of edges.


The total number of nodes in a binary tree is atleast 2n +1 and atmost 2n+1+1.

  • The minimum number of nodes in a binary tree of height h is ‘h’.
  • The number of internal nodes is atleast h and atmost 2h-1.
  • The height of a binary tree with n nodes atleast (logn+1) and atmost n.

Types of a Binary tree

We have so many binary trees such as:

  • Complete binary tree
  • Almost complete binary tree
  • Strictly binary tree
  • Left skewed binary tree
  • Right skewed binary tree

Complete Binary tree

It is a binary tree in which all leaves are at same depth . The total number of nodes at each level has 2i.

  • The total number of nodes in a complete binary tree has 2h+1-1,

where h is the height of the tree.

Almost complete binary tree

  • It is a binary tree which has two rules:
  • Each node has left child, wherever it has a right child that means it is always left child but for a left child there may not be a right child.
  • The leaf in a tree must be present at height of h or h-1.

Strictly Binary tree

A binary tree is a strictly binary tree if and only if each node has exactly two child nodes or no nodes.

Left skewed binary tree 

A binary tree is a left skewed binary tree if and only if which is each node having its left child only.

Right skewed Binary tree

A binary tree is a right skewed binary tree if and only if which has each node having its right child only.

Binary tree can be represented in any way of the following two ways:

  • Using an array(Linear representation)
  • Using a linked list(Linked representation)

  • Using an array(Linear representation)

A binary tree can be stored represented by using arrays, which is called sequential or linear represntation. This type of represent is static means that a block of memory for an array is to be accurated before going to store the actual data.

  • In this representation, the nodes of the tree are stored level by level starting from the root node . The root node of the tree is stored in the first memory location of allocated memory.
  • The following rules are used to decide the location of any node in the tree structure:
  • The root node is at location 1.

For any node with index i, 1≤i≤n

a) Parent of (i) =i/2

b) Left child (i) =2i

c) Right child(i) =2i+1


  • The data are stored without any pointers.
  • Any node can be accessed by calculating the indexes.
  • Simplicity
  • Static memory allocation.


Array representation is not suitable for normal binary tree, but it is only ideal for complete binary tree.

  • Here most of the array a trees are empty means that more memory is wasted unnecessarily.
  • Additions and delicious of nodes are inefficient because of the data moments in the array.
  • To overcome all these problems by using linked list representation.

Using a linked list representation

  • The binary tree can be represented by using dynamic memory allocation of a node in the linked list form. It contains three fields.

a) Info(data) :It contains the actual data of a node.

b) Left link(left) :It contains the address of the left sub- tree.

c) Right link(right) :It contains the address of the right sub-tree.

When a node has no childrens, the corresponding pointers fields(left, right) are “NULL”.


  • No wastage of memory.
  • Insertions and deletions involves no data moment.
  • Dynamic memory allocations.


  • In this the pointer fields occupy more space than data field.
  • Programming languages which do not support dynamic memory allocation have difficulty in implementing binary tree.
0 like 0 dislike
by Goeduhub's Expert (2.2k points)
edited by

Python Program to implement General TREE

# Python program to implement Normal Tree 

# TreeNode class that has data and a list of children and parent

class TreeNode:

    def __init__(selfdata): = data

        self.children = []

        self.parent = None

    #get tree height here

    def get_level(self):

        level = 0

        p = self.parent

        while p:

            level += 1

            p = p.parent

        return level

    #here we will print tree

    def tree_print(self):

        spaces = ' ' * self.get_level() * 3

        prefix = spaces + "|__" if self.parent else ""

        print(prefix +

        if self.children:

            for child in self.children:


    def add_child(selfchild):

        child.parent = self


def build_ds_tree():

    # create root by making object of Treenode class

    root = TreeNode("Data Structures")

    Primitive = TreeNode("Primitive")




    NonPrimitive = TreeNode("Non-Primitive")


    Linear = TreeNode("Linear")

    Nonlinear = TreeNode("Non-Linear")













#entry point for code execution

if __name__ == '__main__':



Data Structures 














3.3k questions

7.1k answers


4.6k users


About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © Social::   |  |