Binary trees

Question 1

Preorder reversal - code and traversal order?

Answer 1

Preorder (D,L,R)

void Preorder(Node *root) {
	if (root == null) return;
	printf("%c ", root->data);
	Preorder(root->left);
	Preorder(root->right);
}

Question 2

In-order reversal - code and traversal order?

Answer 2

In-order (L,D,R)

void Inorder(Node *root) {
	if (root == null) return;
	Preorder(root->left);
	printf("%c ", root->data);
	Preorder(root->right);
}

Question 3

Postorder (L,R,D) - code and traversal order?

Answer 3

Postorder (L,R,D)

void Postorder(Node *root) {
	if (root == null) return;
	Preorder(root->left);
	Preorder(root->right);
	printf("%c ", root->data);
}

Question 4

What’s the time and space complexity for depth-first traversal?

Answer 4

• Time complexity = O(n) for all cases
• Space complexity = O(h) — height of the tree.
  Worst O(n),
  Best/average O(log n)

Question 5

What are the depth-first traversal algorithms?

Answer 5

• Preorder
• Inorder
• Postorder

Question 6

What is the breadth-first traversal algorithm?

Answer 6

• Level-order

Question 7

What’s the recipe for level order traversal?

Answer 7

LEVEL ORDER RECIPE (Queue (FIFO)):

1. Create queue with root node as the first item in queue
2. While queue NOT empty -> while loop
3. Dequeue front element (current), add left & right to end of queue

#include
void LevelOrder(Node *root) {
	if (root == null) return;
	queue Q;
	Q.push(root);
	while(!Q.empty()) {
		Node* current = Q.front();
		if(current->left != null) 
			Q.push(current->left);
		if(current->right != null)
			Q.push(current->right);
		Q.pop();
	}
}

Question 8

What’s the time and space complexity of level order traversal?

Answer 8

Time complexity = O(n) — all cases irrespective of tree size

Space-complexity = O(1) — best, O(n) — worst/average

Question 9

C++ syntax: how do you import queue?

Answer 9

include

Question 10

C++ syntax: what’s q.empty() do?

Answer 10

Returns boolean true if queue has 0 items

Question 11

C++ syntax: what’s q.pop() do?

Answer 11

Removes first/next item

Question 12

C++ syntax: what’s q.front() do?

Answer 12

Returns first/next item of the queue without removing it.

Question 13

How do you find the height of a tree recursively with code?

Answer 13

int FindHeight(struct Node *root) {
	if (root == NULL) return -1;
	return max(
		FindHeight(root->left),
		FindHeight(root->right)
	) + 1;
}

Question 14

What are the 4 areas in memory allocation?

Answer 14

• Heap
• Stack
• Global/static
• Code (text)

Question 15

What’s the difference between height count and depth count?

Answer 15

Depth count = the leaf nodes or bottom of the tree

Height = top of the tree or root node (e.g. height = 0 at the leaf nodes, height = 3 at root)