Trees

Basic concepts of Tree data structure is discussed below:

A Tree is a recursive data structure containing the set of one or more data nodes where one node is designated as the root of the tree while the remaining nodes are called as the children of the root.
Nodes of a tree either maintain a parent-child relationship between them or they are sister nodes.
In a general tree, A node can have any number of children nodes but it can have only a single parent.

BASIC TERMINOLOGIES:

Root Node :- The root node or parent node is the topmost node in the tree hierarchy.
Sub Tree :- If the root node is not null, the tree T1, T2 and T3 is called sub-trees of the root node.
Leaf Node :- The node of tree, which doesn't have any child node, is called leaf node. Leaf node is the bottom most node of the tree.
Path :- The sequence of consecutive edges is called path.
Ancestor node :- An ancestor of a node is any predecessor node on a path from root to that node. The root node doesn't have any ancestors.
Degree :- Degree of a node is equal to number of children, a node have.
Level Number :- Each node of the tree is assigned a level number in such a way that each node is present at one level higher than its parent. Root node of the tree is always present at level 0.

TYPES OF TREES:

General Tree :

General Tree stores the elements in a hierarchical order in which the top level element is always present at level 0 as the root element. All the nodes except the root node are present at number of levels. The nodes which are present on the same level are called siblings while the nodes which are present on the different levels exhibit the parent-child relationship among them.

Forests :

Forest can be defined as the set of disjoint trees which can be obtained by deleting the root node and the edges which connects root node to the first level node.

Binary Tree :

Binary tree is a data structure in which each node can have at most 2 children. The node present at the top most level is called the root node. A node with the 0 children is called leaf node. Binary Trees are used in the applications like expression evaluation and many more.

Binary Search Tree :

Binary search tree is an ordered binary tree. All the elements in the left sub-tree are less than the root while elements present in the right sub-tree are greater than or equal to the root node element. Binary search trees are used in searching, sorting, etc.

Expression Tree

Expression trees are used to evaluate the simple arithmetic expressions. Expression tree is basically a binary tree where internal nodes are represented by operators while the leaf nodes are represented by operands. Expression trees are widely used to solve algebraic expressions like (a+b)*(a-b).

Tournament Tree

Tournament tree are used to record the winner of the match in each round being played between two players. Tournament tree can also be called as selection tree or winner tree. At the top most level, the winner of the tournament is present as the root node of the tree

BINARY TREE

Creating a tree from an array and three different types of traversals

import java.util.*;

    class Node

        int data;

        Node left, right;

        Node(int data)

            this.data = data;

            this.left = null;

            this.right = null;

public class Main

    public static Node insertLevelOrder(int[] arr, Node root, int i)

        if (i < arr.length)

            Node temp = new Node(arr[i]);

            root = temp;

            root.left = insertLevelOrder(arr, root.left,2 * i + 1);

            root.right = insertLevelOrder(arr, root.right,2 * i + 2);

        return root;

    public static void inOrder(Node root)

        if (root != null)

            inOrder(root.left);

            System.out.print(root.data + " ");

            inOrder(root.right);

    public static void preOrder(Node root)

        if (root != null)

            System.out.print(root.data + " ");

            inOrder(root.left);

            inOrder(root.right);

    public static void postOrder(Node root)

        if (root != null)

            inOrder(root.left);

            inOrder(root.right);

            System.out.print(root.data + " ");

    public static void main(String args[])

        Scanner sc=new Scanner(System.in);

        int size=sc.nextInt();

        int[] arr = new int[size];

        for(int index=0;index<size;index++)

            arr[index]=sc.nextInt();

        Node root=new Node(0);

        root = insertLevelOrder(arr, root, 0);

        System.out.println("Inorder Tree :");

        inOrder(root);

        System.out.println();

        System.out.println("\nPreorder Tree :");

        preOrder(root);

        System.out.println();

        System.out.println("\nPostorder Tree :");

        postOrder(root);

input 1:

1 2 3 4 5 6 7 8 9

output 1:

Inorder Tree :

8 4 9 2 5 1 6 3 7

Preorder Tree :

1 8 4 9 2 5 6 3 7

Postorder Tree :

8 4 9 2 5 6 3 7 1

input 2:

1 2 3 4 5 6

output 2:

Inorder Tree :

4 2 5 1 6 3

Preorder Tree :

1 4 2 5 6 3

Postorder Tree :

4 2 5 6 3 1

Find symmetric tree or not(based on values of the nodes)

import java.util.*;

class Node

  int data;

 Node left = null, right = null;

 Node(int data) {

  this.data = data;

public class Main

    static boolean isSymmetric(Node root1,Node root2)

        if(root1==null&&root2==null)

            return true;

        if(root1.data!=root2.data)

            return false;

        return isSymmetric(root1.left,root2.right)&&isSymmetric(root1.right,root2.left);

    static boolean isSymmetric(Node root)

        return isSymmetric(root.left,root.right);

 public static void main(String[] args)

  Node root = new Node(1);

  root.left = new Node(3);

  root.right = new Node(3);

  root.left.left=new Node(4);

  root.left.right = new Node(6);

  root.right.left = new Node(6);

  root.right.right=new Node(4);

  if (isSymmetric(root)) {

   System.out.print("Yes");

  } else {

   System.out.print("No");

output 1:

yes

explanation 1:

         /   \

        /     \

       3       3

      / \     / \

     4   6   6   4

output 2:

no

explanation 2:

           1                      1                     1

         /   \                   / \                   / \

        /     \                 /   \                 /   \

       3       3     (or)      3     3     (or)      3     3

      / \     / \             /                             \

     4   6   4   6           4                               6

or some other changes...

Find symmetric tree or not(based on structure of the tree)

import java.util.*;

class Node

  int data;

 Node left = null, right = null;

 Node(int data) {

  this.data = data;

public class Main

    static boolean isSymmetric(Node root1,Node root2)

        if(root1==null&&root2==null)

            return true;

        return isSymmetric(root1.left,root2.right)&&isSymmetric(root1.right,root2.left);

    static boolean isSymmetric(Node root)

        return isSymmetric(root.left,root.right);

 public static void main(String[] args)

  Node root = new Node(1);

  root.left = new Node(2);

  root.right = new Node(3);

  root.left.right = new Node(4);

  root.right.left = new Node(5);

  if (isSymmetric(root)) {

   System.out.print("Yes");

  } else {

   System.out.print("No");

output 1:

yes

explanation 1:

           1                    1

         /   \                /   \

        /     \              /     \

       2       3    (or)    2       3

        \     /            / \     / \

         5   6            4   5   6   7

output 2:

no

explanation 2:

           1                   1

         /   \               /   \

        /     \             /     \

       2       3   (or)    2       3

      /       /           /         \

     5       6           5           6

or some other changes...

Find whether the given tree is a complete tree or not

import java.util.*;

class Node

    int data;

    Node left=null, right=null;

    Node(int item)

        data = item;

        left = right = null;

public class Main

    Node root;

    static int size(Node root)

        if(root==null)

            return 0;

        return 1+size(root.left)+size(root.right);

    static boolean isComplete(Node root,int i,int n)

        if(root==null)

            return true;

        if((root.left!=null&&2*i+1>=n)||(!isComplete(root.left,2*i+1,n)))

            return false;

        if((root.right!=null&&2*i+2>=n)||(!isComplete(root.right,2*i+1,n)))

            return false;

        return true;

    public static void main(String args[])

        Node root = new Node(1);

        root.left = new Node(2);

        root.right = new Node(3);

        root.left.left=new Node(4);

        root.left.right = new Node(5);

        root.right.left = new Node(6);

        root.right.right=new Node(7);

        int node_count = size(root);

        int index = 0;

        if (isComplete(root, index, node_count))

            System.out.print("The binary tree is complete");

        else

            System.out.print("The binary tree is not complete");

output 1:

The binary tree is complete

explanation 1:

           1                          1

         /   \                      /   \

        /     \                    /     \

       2       3        (or)      2       3

      / \     / \                / \     /

     4   5   6   7              4   5   6

output 2:

The binary tree is not complete

explanation 2:

         /   \

        /     \

       3       3

      / \       \

     4   5       7

and some other changes too..

Page updated

Google Sites

Report abuse