Which node is the root

A tree is a non-linear abstract data type with a hierarchy-based structure. It consists of nodes (where the data is stored) that are connected via links. The tree data structure stems from a single node called a root node and has subtrees connected to the root.

Tree is a non-linear data structure which organizes data in hierarchical structure and this is a recursive definition.

Tree data structure is a collection of data (Node) which is organized in hierarchical structure recursively

In tree data structure, every individual element is called as Node. Node in a tree data structure stores the actual data of that particular element and link to next element in hierarchical structure.

In a tree data structure, if we have N number of nodes then we can have a maximum of N-1 number of links.

Array Method

In this method, a binary tree is represented using a single-dimensional array. So for this purpose, the root node will be considered at zero index position. Based on the position of the parent, the left and right child will be calculated. So, the left child will be placed at ‘2n+1’ and the right child will place at ‘2n+2’. Here n is the position of parent.

In this tree, ‘a’ is the root node so it will be placed at zero index in an array. 

For the index position of left child ‘b’ :

 For the index location of the right child ‘c’:

For the index location of the left child of ‘d’:

For the index location of the right child of ‘e’:

For the index location of the left child of ‘f’:

 For the index location of the left child of ‘g’:

The tree is a non-linear data structure. This structure is mainly used to represent data containing a hierarchal relationship between elements (For example) record, family relationship, and table contents. The earth structure is a good example of a tree.

All data elements are in trees are called nodes. The node, which does not have its preceding nodes, is called ROOT node and it is considered at level number one. If a tree has ROOT node N and S1 and S2 left and right successor then N is called parent or father and S1 is called left child and S2 is called the right child. S1 and S2 are called brothers or siblings. The node on the same level is called “NODE OF THE SAME GENERATION”.

Linked List Method

In this, a double-linked list will be used to represent every single node of the binary tree. In a doubly-linked list, there will be three fields i.e. address of the left child, root and address of right child fields.

Let us consider an example in which a binary tree has been taken with two children on each node. ’a’ is the root node in this tree. Every node has a left and right pointer. The left pointer will point towards the left child of the node and the right pointer will point towards the right node. The left and child addresses for leaf nodes will be assigned as ‘Null Address’.

Binary Tree Traversals

A binary tree consists of different nodes. So there are three methods to traverse a tree:

• Node: It is an element of a tree.

• Root: It is the starting node of a tree. It is the top most element that has no parent element.

• Parent Node: It is the node that has branches from top to bottom. It is the immediate predecessor of any node.

• Child Node: It is the node that has a node from bottom to top. It is the instantaneous successor of any node.

• Level: Each step in a tree is level.

• Leaf Node: It is the node having no child.

• Non-Leaf Node: It is the node having at least one child.

• Edge: It is the link between two nodes.

• Sibling: It is the child node with the same parents.

• Internal Nodes: These are the nodes that have child nodes.

• Degree: It is the largest number of child nodes.

• Path: It is a sequence of nodes along with the boundaries of a tree.

In a binary tree,  every node in a tree should have a maximum of two children. It means that a tree can constitute either 0, 1, or 2 nodes. Let’s consider a tree shown below. In this figure, node ‘a’ has two children(b and f). Similarly, node b has also two children (d and e) and the same for node f.  And node ‘f ’ has also two children (g and h) Each node has a maximum of two children. A binary tree usually consists of three nodes:

Перед прочтением этой статьи настоятельно рекомендуется ознакомиться с первой частью: Splay-дерево. Поиск

Как упоминалось в предыдущей статье, Splay-дерево — это самобалансирующаяся структура данных, в которой последний ключ, к которому осуществлялся доступ, всегда помещается в корень. Операция вставки аналогична вставке в бинарное дерево поиска с несколькими дополнительными шагами, цель которых убедиться, что вновь вставленный ключ становится новым корнем.

Ниже приведены различные случаи при вставке ключа k в Splay-дерево.

1) Корень равен NULL: мы просто создаем новый узел и возвращаем его как корневой.

2) Выполняем операцию Splay над заданный ключом k. Если k уже присутствует, он становится новым корнем. Если он отсутствует, то новым корневым узлом становится последний узел-лист, к которому был осуществлен доступ.

3) Если новый корневой ключ такой же, как k, ничего не делаем, поскольку k уже существует.

4) В противном случае выделяем память для нового узла и сравниваем корневой ключ с k.

4.a) Если k меньше корневого ключа, делаем корень правым дочерним элементом нового узла, копируем левый дочерний элемент корня в качестве левого дочернего элемента нового узла и делаем левый дочерний элемент корня равным NULL.

4.b) Если k больше корневого ключа, делаем корень левым дочерним элементом нового узла, копируем правый дочерний элемент корня в качестве правого дочернего элемента нового узла и делаем правый дочерний элемента корня равным NULL.

5) Возвращаем новый узел в качестве нового корня дерева.

 100 [20] 25 / \ \ / \ 50 200 50 20 50 / insert(25) / \ insert(25) / \ 40 ======> 30 100 ========> 30 100 / 1. Splay(25) \ \ 2. insert 25 \ \ 30 40 200 40 200 / [20] 

С++

#include <bits/stdc++.h>
using namespace std;
// Узел АВЛ-дерева
class node
{ public: int key; node *left, *right;
};
/* Вспомогательная функция, которая выделяет
новый узел с заданным key и left и right, указывающими в NULL. */
node* newNode(int key)
{ node* Node = new node(); Node->key = key; Node->left = Node->right = NULL; return (Node);
}
// Служебная функция для разворота поддерева с корнем y вправо.
// Смотрите диаграмму, приведенную выше.
node *rightRotate(node *x)
{ node *y = x->left; x->left = y->right; y->right = x; return y;
}
// Служебная функция для разворота поддерева с корнем x влево
// Смотрите диаграмму, приведенную выше.
node *leftRotate(node *x)
{ node *y = x->right; x->right = y->left; y->left = x; return y;
}
// Эта функция поднимет ключ
// в корень, если он присутствует в дереве.
// Если такой ключ отсутствует в дереве, она
// поднимет в корень самый последний элемент,
// к которому был осуществлен доступ.
// Эта функция изменяет дерево
// и возвращает новый корень (root).
node *splay(node *root, int key)
{ // Базовые случаи: root равен NULL или // ключ находится в корне if (root == NULL || root->key == key) return root; // Ключ лежит в левом поддереве if (root->key > key) { // Ключа нет в дереве, мы закончили if (root->left == NULL) return root; // Zig-Zig (Левый-левый) if (root->left->key > key) { // Сначала рекурсивно поднимем // ключ в качестве корня left-left root->left->left = splay(root->left->left, key); // Первый разворот для root, // второй разворот выполняется после else root = rightRotate(root); } else if (root->left->key < key) // Zig-Zag (Left Right) { // Сначала рекурсивно поднимаем // ключ в качестве кореня left-right root->left->right = splay(root->left->right, key); // Выполняем первый разворот для root->left if (root->left->right != NULL) root->left = leftRotate(root->left); } // Выполняем второй разворот для корня return (root->left == NULL)? root: rightRotate(root); } else // Ключ находится в правом поддереве { // Ключа нет в дереве, мы закончили if (root->right == NULL) return root; // Zag-Zig (Правый-левый) if (root->right->key > key) { // Поднять ключ в качестве кореня right-left root->right->left = splay(root->right->left, key); // Выполняем первый поворот для root->right if (root->right->left != NULL) root->right = rightRotate(root->right); } else if (root->right->key < key)// Zag-Zag (Правый-правый) { // Поднимаем ключ в качестве корня // right-right и выполняем первый разворот root->right->right = splay(root->right->right, key); root = leftRotate(root); } // Выполняем второй разворот для root return (root->right == NULL)? root: leftRotate(root); }
}
// Функция для вставки нового ключа k в splay-дерево с заданным корнем
node *insert(node *root, int k)
{ // Простой случай: если дерево пусто if (root == NULL) return newNode(k); // Делаем ближайший узел-лист корнем root = splay(root, k); // Если ключ уже существует, то возвращаем его if (root->key == k) return root; // В противном случае выделяем память под новый узел node *newnode = newNode(k); // Если корневой ключ больше, делаем корень правым дочерним элементом нового узла, копируем левый дочерний элемент корня в качестве левого дочернего элемента нового узла if (root->key > k) { newnode->right = root; newnode->left = root->left; root->left = NULL; } // Если корневой ключ меньше, делаем корень левым дочерним элементом нового узла, копируем правый дочерний элемент корня в качестве правого дочернего элемента нового узла else { newnode->left = root; newnode->right = root->right; root->right = NULL; } return newnode; // новый узел становится новым корнем
}
// Служебная функция для вывода
// обхода в дерева ширину.
// Функция также выводит высоту каждого узла
void preOrder(node *root)
{ if (root != NULL) { cout<<root->key<<" "; preOrder(root->left); preOrder(root->right); }
}
/* Управляющий код */
int main()
{ node *root = newNode(100); root->left = newNode(50); root->right = newNode(200); root->left->left = newNode(40); root->left->left->left = newNode(30); root->left->left->left->left = newNode(20); root = insert(root, 25); cout<<"Preorder traversal of the modified Splay tree is \n"; preOrder(root); return 0;
}
// Этот код любезно предоставлен rathbhupendra

C

// Код позаимствован c http://algs4.cs.princeton.edu/33balanced/SplayBST.java.html
#include<stdio.h>
#include<stdlib.h>
// Узел АВЛ-дерева
struct node
{ int key; struct node *left, *right;
};
/* Вспомогательная функция, которая создает
новый узел с заданным key и left и right, указывающими в NULL. */
struct node* newNode(int key)
{ struct node* node = (struct node*)malloc(sizeof(struct node)); node->key = key; node->left = node->right = NULL; return (node);
}
// Служебная функция для разворота поддерева с корнем y вправо.
// Смотрите диаграмму, приведенную выше.
struct node *rightRotate(struct node *x)
{ struct node *y = x->left; x->left = y->right; y->right = x; return y;
}
// Служебная функция для разворота поддерева с корнем x влево
// Смотрите диаграмму, приведенную выше.
struct node *leftRotate(struct node *x)
{ struct node *y = x->right; x->right = y->left; y->left = x; return y;
}
// Эта функция поднимет ключ
// в корень, если он присутствует в дереве.
// Если такой ключ отсутствует в дереве, она
// поднимет в корень самый последний элемент,
// к которому был осуществлен доступ.
// Эта функция изменяет дерево
// и возвращает новый корень.
struct node *splay(struct node *root, int key)
{ // Базовые случаи: корень равен NULL или // ключ находится в корне if (root == NULL || root->key == key) return root; // Ключ лежит в левом поддереве if (root->key > key) { // Ключа нет в дереве, мы закончили if (root->left == NULL) return root; // Zig-Zig (Левый-левый) if (root->left->key > key) { // Сначала рекурсивно поднимем // ключ как корень left-left root->left->left = splay(root->left->left, key); // Первый разворот для корня, // второй разворот выполняется после else root = rightRotate(root); } else if (root->left->key < key) // Zig-Zag (Левый-правый) { // Сначала рекурсивно поднимаем // ключ как корень left-right root->left->right = splay(root->left->right, key); // Выполняем первый разворот для root->left if (root->left->right != NULL) root->left = leftRotate(root->left); } // Выполняем второй разворот для корня return (root->left == NULL)? root: rightRotate(root); } else // Ключ находится в правом поддереве { // Ключа нет в дереве, мы закончили if (root->right == NULL) return root; // Zag-Zig (Правый-левый) if (root->right->key > key) { //Поднимаем ключ в качестве корня right-left root->right->left = splay(root->right->left, key); // Выполняем первый поворот для root->right if (root->right->left != NULL) root->right = rightRotate(root->right); } else if (root->right->key < key)// Zag-Zag (Правый-правый) { // Поднимаем ключ в качестве корня // right-right и выполняем первый разворот root->right->right = splay(root->right->right, key); root = leftRotate(root); } //Выполняем второй разворот для корня return (root->right == NULL)? root: leftRotate(root); }
}
// Функция для вставки нового ключа k в splay-дерево с заданным корнем
struct node *insert(struct node *root, int k)
{ // Простой случай: если дерево пусто if (root == NULL) return newNode(k); // Делаем ближайший узел-лист корнем root = splay(root, k); // Если ключ уже существует, то возвращаем его if (root->key == k) return root; // В противном случае выделяем память под новый узел struct node *newnode = newNode(k); // Если корневой ключ больше, делаем корень правым дочерним элементом нового узла, копируем левый дочерний элемент корня в качестве левого дочернего элемента нового узла if (root->key > k) { newnode->right = root; newnode->left = root->left; root->left = NULL; } // Если корневой ключ меньше, делаем корень левым дочерним элементом нового узла, копируем правый дочерний элемент корня в качестве правого дочернего элемента нового узла else { newnode->left = root; newnode->right = root->right; root->right = NULL; } return newnode; // новый узел становится новым корнем
}
// Служебная функция для вывода
// обхода в дерева ширину.
// Функция также выводит высоту каждого узла
void preOrder(struct node *root)
{ if (root != NULL) { printf("%d ", root->key); preOrder(root->left); preOrder(root->right); }
}
/* Управляющий код для проверки приведенной выше функции */
int main()
{ struct node *root = newNode(100); root->left = newNode(50); root->right = newNode(200); root->left->left = newNode(40); root->left->left->left = newNode(30); root->left->left->left->left = newNode(20); root = insert(root, 25); printf("Preorder traversal of the modified Splay tree is \n"); preOrder(root); return 0;
}

Вывод:

Preorder traversal of the modified Splay tree is
25 20 50 30 40 100 200

Sub Tree

In a tree data structure, each child from a node forms a subtree recursively. Every child node will form a subtree on its parent node.

Complete Binary Tree

This is also called the “perfect binary tree”. In this, all levels are completely filled. And every node in each level must have two children and each level must comprising of 2N nodes. Where ‘N’ is the level number. And the last level has nodes as left as possible.

Properties of Complete Binary Tree

1. The maximum range of nodes in it are:

And x=  Tree height.

2. The minimum range of nodes in it are:

3. Its maximum height for ‘n’ number of nodes is:

4. Its minimum height for ‘n’ number of nodes is:

Similar Binary Tree

Two binary trees T1 and T2 are said to be a similar binary trees if they have the same structure. In simple words, we say that if two trees have the same shape then they are called similar trees.

Complete Binary Tree

A tree is said to be a complete binary tree if it has exactly two nodes except the last node.

Threaded Binary Tree

Traversing a binary tree is a common operation and it would be helpful to find a more efficient method for implementing the traversal. Moreover, half of the entries in the Lchild and Rchild field will contain an NULL pointer. These fields may be used more efficiently by replacing the NULL entries with special pointers which point to nodes higher in the tree. Such types of special pointers are called threads and binary trees with such pointers are called threaded binary trees.

Copy of Tree Data Structure

Two binary tree T1 and T2 are said to be copy of each other if they have same structure and same contents.

Binary Tree Representation Using Linked List Representation:

The most popular and practical way of representing a binary tree is using a linked list (or pointers). In the linked list, every element is represented as a node. A node consists of three fields such as :

• Left Child (Lchild)
• Information of the Node (Info)
• Right Child (Rchild)

struct Tree
{ int information; struct Tree *Lchild; struct Tree *Rchild;
}

Operation On Binary Tree

• Create an empty binary tree
• Traversing a binary tree
• Inserting a Binary Tree
• Deleting a Node
• Searching for a Node
• Copying the mirror image of a tree
• Determine the total no: of Nodes
• Determine the total no: leaf Nodes
• Determine the total no: non-leaf Nodes
• Find the smallest element in a Node
• Finding the largest element
• Find the Height of the tree
• Finding the Father/Left Child/Right Child/Brother of an arbitrary node

Traversing of Binary tree data structure:

1. Pre Order Traversing: –
   • Visit the ROOT node.
   • Traverse the LEFT subtree in pre-order.
   • Traverse the RIGHT subtree in pre-order.
2. In Order Traversing: –
   • Traverse the LEFT subtree in pre-order.
   • Visit the ROOT node.
   • Traverse the RIGHT subtree in pre-order.
3. Post Order Traversing: –
   • Traverse the LEFT subtree in pre-order.
   • Traverse the RIGHT subtree in pre-order.
   • Visit the ROOT node.

[a +(b-c)] * [d –c) / (f + g –h)]

Pre order traversing:

* + a - b c / - d e - + f g h

Post Order traversing:

a b c - + d e - f g + h - / *

Inorder Traversal

Left Child >> Root Node >> Right Child

In the above tree, a root node is ‘a’ while left and right nodes are ‘b’ and ‘c’.Its inorder traversal will be:

Balanced Binary Tree

A balanced binary tree is one in which the largest path through the left subtree is the same length as the largest path of the right subtree, i.e., from root to leaf. Searching time is very less in balanced binary trees compared to unbalanced binary trees. i.e., balanced trees are used to maximize the efficiency of the operations on the tree.

There are two types of balanced trees :

• Height Balanced Trees
• Weight Balanced Trees

1. Height Balanced Trees

In height-balanced trees balancing the height is the important factor. There are two main approaches, which may be used to balance (or decrease) the depth of a binary tree :

• Insert a number of elements into a binary tree in the usual way, using the algorithm given in the previous section (i.e., Binary search Tree insertion). After inserting the elements, copy the tree into another binary tree in such a way that the tree is balanced. This method is efficient if the data(s) are continually added to the tree.
• Another popular algorithm for constructing a height-balanced binary tree is the AVL tree, which is discussed in the next section.

2. Weight Balanced Trees

A weight-balanced tree is a balanced binary tree in which an additional weight field is also there. The nodes of a weight-balanced tree contain four fields:

• Data Element
• Left Pointer
• Right Pointer
• A probability or weight field

The data element left and right pointer fields are save as that in any other tree node. The probability field is a specially added field for a weight-balanced tree. This field holds the probability of the node being accessed again, that is the number of times the node has been previously searched for.

Left Skewed Binary Tree

It consists of nodes consisting of only left children. It has only left subtree or only left children. It is the left side-dominated tree. All the right side children remain null.

Let us consider an example as shown below. In this, the root node is ‘a’ and the leaf node is ‘d’. While internal nodes are ‘b’ and ‘d’.

AVL Tree Data structure

This algorithm was developed in 1962 by two Russian Mathematicians, G.M. Adel’s son Vel’sky and E.M. Landis; here the tree is called AVL Tree. An AVL tree is a binary tree in which the left and right subtree of any node may differ in height by at most 1, and in which both the subtrees are themselves AVL Trees.

• A node is called left heavy if the largest path in its left subtree is one level larger than the largest path of its right subtree.
• A node is called right heavy if the largest path in its right subtree is one level larger than the largest path of its left subtree.
• The node is called balanced if the largest paths in both the right and left subtrees are equal.

Root

In a tree data structure, the first node is called as Root Node. Every tree must have a root node. We can say that the root node is the origin of the tree data structure. In any tree, there must be only one root node. We never have multiple root nodes in a tree.

Siblings

In a tree data structure, nodes which belong to same Parent are called as SIBLINGS. In simple words, the nodes with the same parent are called Sibling nodes.

Path

In a tree data structure, the sequence of Nodes and Edges from one node to another node is called as PATH between that two Nodes. Length of a Path is total number of nodes in that path. In below example the path A — B — E — J has length 4.

Types of Binary Tree

• Full Binary Tree.

• Perfect Binary Tree.

• Almost Complete Binary Tree.

• Complete Binary Tree.

• Left Skewed Binary Tree.

• Right Skewed Binary Tree

• Balanced Binary Tree

Example

Expression Tree Data structure

An ordered tree may be used to represent a general expression, which is called an expression tree. Nodes in one expression tree contain operators and operands.

Internal Nodes

In a tree data structure, the node which has atleast one child is called as INTERNAL Node. In simple words, an internal node is a node with atleast one child.

In a tree data structure, nodes other than leaf nodes are called as Internal Nodes. The root node is also said to be Internal Node if the tree has more than one node.

Internal nodes are also called as ‘Non-Terminal‘ nodes.

Height

In a tree data structure, the total number of edges from leaf node to a particular node in the longest path is called as HEIGHT of that Node. In a tree, height of the root node is said to be height of the tree. In a tree, height of all leaf nodes is ‘0’.

Important Terms

• Path − Path refers to the sequence of nodes along the edges of a tree.

• Root − The node at the top of the tree is called root. There is only one root per tree and one path from the root node to any node.

• Parent − Any node except the root node has one edge upward to a node called parent.

• Child − The node below a given node connected by its edge downward is called its child node.

• Leaf − The node which does not have any child node is called the leaf node.

• Subtree − Subtree represents the descendants of a node.

• Visiting − Visiting refers to checking the value of a node when control is on the node.

• Traversing − Traversing means passing through nodes in a specific order.

• Levels − Level of a node represents the generation of a node. If the root node is at level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.

• Keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Basic Terminologies

• The root is a specially designed node (or data items) in a tree. It is the first node in the hierarchical arrangement of the data items. Each data item in a tree is called a node. It specifies the data information and links (branches) to other data items.
• A node is a structure that may contain a value, a condition, or represent a separate data structure (which could be a tree of its own). Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees are drawn growing downwards). A node that has a child is called the child’s parent node (or ancestor node, or superior). A node has at most one parent
• An internal node (also known as an inner node or branch node) is any node of a tree that has child nodes.
• Similarly, an external node (also known as an outer node, leaf node, or terminal node) is any node that does not have child nodes.
• The topmost node in a tree is called the root node. Being the topmost node, the root node will not have a parent. It is the node at which operations on the tree commonly begin (although some algorithms begin with the leaf nodes and work up ending at the root). All other nodes can be reached from it by following edges or links. (In the formal definition, each such path is also unique). In some trees, such as heaps, the root node has special properties. Every node in a tree can be seen as the root node of the subtree rooted at that node. A free tree is a tree that is not rooted.
• The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree.
• The depth of a node is the length of the path to its root (i.e., its root path). This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. Conventionally, the value −1 corresponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node.
• A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T. (This is different from the formal definition of subtree used in graph theory.) The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree (in analogy to the term proper subset).

A tree is said to be a binary tree if it has at most two nodes. In simple words, we say that a binary tree must have zero, one, or two nodes. A binary tree is a very important tree structure.

Parent

In a tree data structure, the node which is a predecessor of any node is called as PARENT NODE. In simple words, the node which has a branch from it to any other node is called a parent node. Parent node can also be defined as «The node which has child / children«.

Leaf

In a tree data structure, the node which does not have a child is called as LEAF Node. In simple words, a leaf is a node with no child.

In a tree data structure, the leaf nodes are also called as External Nodes. External node is also a node with no child. In a tree,

leaf node is also called as ‘Terminal‘ node.

Almost Complete Binary Tree

It is also named an “incomplete binary tree”. In this sort of binary tree, every single node must have two children in all levels apart from the last level but the first left child should be filled and then the right one.

Let us consider an example below. In this , there are a total five levels(0,1,2,3,4). In level 1, there are a total of 2 nodes in which each of the nodes has two children. Similarly, level 2 has 4 and level 3 has 8 nodes with their corresponding two children. Then we have two leaf nodes x and y at the end which are filled from left to right.

Right Skewed Binary Tree

In this type of binary tree, there exist nodes consisting of only the right children. It is vice versa of the left-skewed binary tree. It is a right-side-dominated tree. It contains no left child. 

7. Balanced Binary Tree

In this, the height of the left subtree and right subtree of every single node might vary by one.

Binary Tree Representation

A binary tree can be represented by two methods.

• Using Array Method

• Using the Linked List Method

Edge

In a tree data structure, the connecting link between any two nodes is called as EDGE. In a tree with ‘N‘ number of nodes there will be a maximum of ‘N-1‘ number of edges.

Types of Trees

There are three types of trees −

• Binary Search Trees

General Trees

General trees are unordered tree data structures where the root node has minimum 0 or maximum ‘n’ subtrees.

The General trees have no constraint placed on their hierarchy. The root node thus acts like the superset of all the other subtrees.

Binary Trees

Binary Trees are general trees in which the root node can only hold up to maximum 2 subtrees: left subtree and right subtree. Based on the number of children, binary trees are divided into three types.

Full Binary Tree

• A full binary tree is a binary tree type where every node has either 0 or 2 child nodes.

Complete Binary Tree

• A complete binary tree is a binary tree type where all the leaf nodes must be on the same level. However, root and internal nodes in a complete binary tree can either have 0, 1 or 2 child nodes.

Perfect Binary Tree

• A perfect binary tree is a binary tree type where all the leaf nodes are on the same level and every node except leaf nodes have 2 children.

Binary Search Trees

Binary Search Trees possess all the properties of Binary Trees including some extra properties of their own, based on some constraints, making them more efficient than binary trees.

The data in the Binary Search Trees (BST) is always stored in such a way that the values in the left subtree are always less than the values in the root node and the values in the right subtree are always greater than the values in the root node, i.e. left subtree < root node ≤ right subtree.

Advantages of BST

• Binary Search Trees are more efficient than Binary Trees since time complexity for performing various operations reduces.

• Since the order of keys is based on just the parent node, searching operation becomes simpler.

• The alignment of BST also favors Range Queries, which are executed to find values existing between two keys. This helps in the Database Management System.

Disadvantages of BST

The main disadvantage of Binary Search Trees is that if all elements in nodes are either greater than or lesser than the root node, the tree becomes skewed. Simply put, the tree becomes slanted to one side completely.

This skewness will make the tree a linked list rather than a BST, since the worst case time complexity for searching operation becomes O(n).

To overcome this issue of skewness in the Binary Search Trees, the concept of Balanced Binary Search Trees was introduced.

Balanced Binary Search Trees

Consider a Binary Search Tree with ‘m’ as the height of the left subtree and ‘n’ as the height of the right subtree. If the value of (m-n) is equal to 0,1 or -1, the tree is said to be a Balanced Binary Search Tree.

The trees are designed in a way that they self-balance once the height difference exceeds 1. Binary Search Trees use rotations as self-balancing algorithms. There are four different types of rotations: Left Left, Right Right, Left Right, Right Left.

There are various types of self-balancing binary search trees −

• Red Black Trees

• Priority Search Trees

Level

Depth

In a tree data structure, the total number of egdes from root node to a particular node is called as DEPTH of that Node. In a tree, the total number of edges from root node to a leaf node in the longest path is said to be Depth of the tree. In simple words, the highest depth of any leaf node in a tree is said to be depth of that tree. In a tree, depth of the root node is ‘0’.

Degree

In a tree data structure, the total number of children of a node is called as DEGREE of that Node. In simple words, the Degree of a node is total number of children it has. The highest degree of a node among all the nodes in a tree is called as ‘Degree of Tree‘

Postorder Traversal

Left Child >> Right Child >> Root Node

To understand its concept, we will consider the previous binary tree. Its postorder traversal will be:

For preorder traversal, we have:

For postorder traversal, we have:

Properties of Binary Tree

1. The maximum range of nodes in it is:

And x= Tree height 

2. The minimum range of nodes in it is:

3. Its maximum height for ‘n’ number of nodes is:

4. Its maximum height tree for ‘n’ number of nodes is:

Application of Binary Tree

• It is used to find duplicate nodes.

• It is also used in sorting and in the traversal.

• Its practical application is in an organization where binary trees are used to organize data in a sequence.

• It is also used in machine learning, database tables, encryption and routing.

Child

In a tree data structure, the node which is descendant of any node is called as CHILD Node. In simple words, the node which has a link from its parent node is called as child node. In a tree, any parent node can have any number of child nodes. In a tree, all the nodes except root are child nodes.

Full Binary Tree

Properties of Full Binary Tree

And x= height of the full binary tree

2. Its minimum range of nodes  is:

3. Its maximum height for ‘n’ nodes is:

4. Its minimum height for ‘n’ nodes is:

5. The range of leaf nodes for ‘n’ internal nodes is :

2. Perfect Binary Tree

In this type, all the internal nodes must have two children and the entire leaf nodes are at a similar level. This can be a full and complete binary tree as well.

To understand, let us consider an example shown below. This binary tree consists of three levels: internal nodes contain two child each and leaf nodes are also at an equal level.

Properties of Perfect Binary Tree

1. The  leaf nodes for ‘x’ height in it are:

   

2. The range of internal nodes in it is:

And x= height of the tree.

3. The maximum range of nodes in it is:

4. The minimum range of nodes in it is:

Recommended Post

If you find any error then you can simply comment below on the tree data structure.

Thank you so much!