Binary Tree

Introduction to Tree:

Tree Data Structure is a hierarchical data structure in which a collection of elements known as nodes are connected to each other via edges such that there exists exactly one path between any two nodes....

Basic Terminologies In Tree Data Structure:

Parent Node: The node which is a predecessor of a node is called the parent node of that node. {B} is the parent node of {D, E}. Child Node: The node that is the immediate successor of a node is called the child node of that node. Examples: {D, E} are the child nodes of {B}. Root Node: The topmost node of a tree or the node that does not have any parent node is called the root node. {A} is the root node of the tree. A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the tree. Leaf Node or External Node: The nodes which do not have any child nodes are called leaf nodes. {K, L, M, N, O, P, G} are the leaf nodes of the tree. Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that node. {A,B} are the ancestor nodes of the node {E} Descendant: Any successor node on the path from the leaf node to that node. {E,I} are the descendants of the node {B}. Sibling: Children of the same parent node are called siblings. {D,E} are called siblings. Level of a node: The count of edges on the path from the root node to that node. The root node has level 0. Internal node: A node with at least one child is called Internal Node. Neighbour of a Node: Parent or child nodes of that node are called neighbors of that node. Subtree: Any node of the tree along with its descendant....

Types of Tree data structures:

Below are types of Tree data structure:...

1. Binary Tree:

In a binary tree, each node can have a maximum of two children linked to it. Some common types of binary trees include full binary trees, complete binary trees, balanced binary trees, and degenerate binary trees....

2. Ternary Tree:

A Ternary Tree is a tree data structure in which each node has at most three child nodes, usually distinguished as “left”, “mid” and “right”....

3. N-ary Tree or Generic Tree:

Generic trees are a collection of nodes where each node is a data structure that consists of records and a list of references to its children(duplicate references are not allowed). Unlike the linked list, each node stores the address of multiple node....

4. Binary Search Tree:

Binary Search Tree is a node-based binary tree data structure which has the following properties:...

6. AVL Tree

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees for any node cannot be more than one....

Previously Asked GATE Questions on Trees:

Question 1: Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true? (GATE CS 2000) (a) LASTIN = LASTPOST (b) LASTIN = LASTPRE (c) LASTPRE = LASTPOST (d) None of the above...