TCS NQT Trees Quiz – 1

Queue works on the first in first out manner. So when we traverse the tree so we can put the node in the queue

Note - Linked List can also be used to implement level order traversal, however, doing level order traversal using stack is more efficient

Height of tree is h then Full Binary Tree will have

• (2^h+1 – 1)nodes  (if h starts from 0)


• (2^h – 1)nodes  (if h starts from 1)

A full binary tree is a binary tree in which every node in the tree has exactly zero or two children.

Click here to read more about types of Binary Trees

There are following types of Binary Trees :

• Tree (n-ary)


• Binary
  
  
  
  • Full
  
  
  • Complete
  
  
  • Perfect
  
  
  • Balanced
  
  
  
  


• Ternary


• Binary Search Tree


• AVL


• Red Black Tree

Full Binary Tree

• A binary tree is said to be a Full binary tree if all nodes except the leaf nodes have either 0 or 2 children. In other words the degree of such tree can either be  0 or 2.


• In the given image, we can see that,
  
  
  
  • nodes ‘a’, ‘b’, ‘e’ have two child nodes each.
  
  
  • nodes ‘c’, ‘d’ have 0 child nodes.
  
  
  
  


• Hence the given example is a full binary tree, also called strict binary tree.

When we want to traverse the tree in inorder  traverser, so we follows this sequence. That is Left Root Right.

Check these page here for Rules and Examples

• Inorder of a Tree


• 10 Examples of Inorder of Tree

Rules and Examples of Calculating Inorder, Postorder, Preorder are given here -

• Inorder PostOrder Preorder


• Inorder postorder Preorder Examples

You can read more about inorder postorder preorder here

• PreOrder : ABDEFCGHJLK


• Inorder: DBFEAGCLJHK

1. We know that in PreOrder of tree the first node is always the root node of the tree right ?


2. We can then search 'A' in the inorder sequence of the tree


3. All elements on left side of 'A' in inorder are left subtree and on right are right subtree


4. Keep on doing the same recursively to obtain the visual representation of tree


5. Finally find postorder of this tree

You can read more about Depth, Height, Level etc formulas and definition on this page here

• The number of edges that lie in between the path from a node to the root in a tree is defined as the depth of the tree. 


• In the image given here, we can see the depth of each node. For instance the depth of the root node is zero.

• At zero level=2^0=1


• At first level=2^1=2


• At second level=2^2=4


• At third level=2^3=8


• So total number node is=1+2+4+8=15.

Depth always starts from 0



So answer is 4

 

You can read more about trees here - 

Some articles say the height of the tree starts from 0 and some say 1. Actually the correct answer is 0.

The definition of height is: Height of a node can be defined as the longest path downwards between the root and a leaf.

Clearly, if a tree has only root node then root and leaf are same and distance is 0 right?

If an MCQ Question comes in the exam, it will generally say - Assume Height starts from (0 or 1), if not then learn both below formulas safe side mark whichever is present.



So the height of the tree is 4.

Explanation: 

The inorder and preorder traversal are ABDEFCGHJLK and DBFEAGCLJHK respectively.
In inorder traversal we follow the sequence that is Left root right and preorder traversal follow the sequence that is Root Left Right. So that from the preorder traversal we can identify root node so from the inorder traversal all the node which are left side of root node that are come left subtree and all the node which are right side of root node that are come right  subtree. Now follow the same process with left and right subtree.