Register

GO Classes DPP | GATE CS, DA | Data Structure | Binary Tree Traversals

359 views
10 10 votes

A binary tree has:

  • $1000$ nodes in the left subtree
     
  • $100$ nodes in the right subtree

How many nodes are processed before the root in preorder, inorder, and postorder traversal respectively?

  1. $0, 1000, 1100$
     
  2. $1000, 0, 1100$
     
  3. $1100, 1000, 0$
     
  4. $0, 1100, 1000$

1 Answer

0 0 votes

The tree has:

$1000$ nodes in the left subtree

$100$ nodes in the right subtree

In preorder traversal, order is:

Root, Left, Right

So, the root is processed first. Number of nodes before root is:

$0$

In inorder traversal, order is:

Left, Root, Right

So, all nodes in the left subtree are processed before the root. Number of nodes before root is:

$1000$

In postorder traversal, order is:

Left, Right, Root

So, all nodes in the left and right subtrees are processed before the root.

Total nodes before root:

$1000 + 100 = 1100$

Therefore, the required values are:

$\boxed{0, 1000, 1100}$

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

10 10 votes
1 1 answer
579
579 views
GO Classes asked Jul 28
579 views
GO Classes DPP | GATE CS, DA | Data Structure | AVL Tree
Rebalance the following tree so that it becomes a valid AVL tree:What will be the root after rebalancing?$10$ $12$ $16$ $20$
7 7 votes
1 1 answer
407
407 views
GO Classes asked Jul 28
407 views
GO Classes DPP | GATE CS, DA | Data Structure | Collision-Free Hash Parameter
For the keys:$47, 61, 36, 52, 56, 33, 92$consider the hash function:$h(k) = ((10k + 4) \bmod c) \bmod 7$Find the smallest positive integer $c$ such that no collisions occ...
4 4 votes
1 1 answer
306
306 views
GO Classes asked Jul 28
306 views
GO Classes DPP | GATE CS, DA | Data Structure | Heap Insertion
Suppose vector $A$ is a min-heap:$A = [2, 4, 3, 6, 7, 3, 5, 8, 9]$After calling $\texttt{Push(1)}$, what is the final heap array?$[1, 2, 3, 6, 4, 3, 5, 8, 9, 7]$ $[1, 4, ...
5 5 votes
1 1 answer
265
265 views
GO Classes asked Jul 28
265 views
GO Classes DPP | GATE CS, DA | Data Structure | Hash Table
Which of the following statements are true?$\text{S1}$. The worst-case complexity of checking whether an object is present in a hash set is $O(1)$.$\text{S2}$. The worst-...