Trees

Question 1

What is a Tree?

Answer 1

A tree is a widely used abstract data type that represents a hierarchical structure with a set of connected nodes. Each node in the tree can be connected to many children, but must be connected to exactly one parent, except for the root node, which has no parent.

Question 2

Components of a tree?

Answer 2

-A tree is an undirected and connected acyclic graph.
-There are no cycles or loops. Each node can be like the root node of its own subtree, making recursion a useful technique for tree traversal.

Question 3

Neighbor

Answer 3

Parent or child of a node

Question 4

Ancestor

Answer 4

A node reachable by traversing its parent chain

Question 5

Descendant

Answer 5

A node in the node’s subtree

Question 6

Degree

Answer 6

Number of children of a node

Question 7

Width

Answer 7

Number of nodes in a level

Question 8

Level/Depth

Answer 8

Number of edges along the unique path between a node and the root node

Question 9

Binary tree

Answer 9

Binary means two, so nodes in a binary tree have a maximum of two children.

Question 10

Complete binary tree

Answer 10

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Question 11

Balanced binary tree

Answer 11

A binary tree structure in which the left and right subtrees of every node differ in height by no more than 1.

Question 12

In-order traversa

Answer 12

Left -> Root -> Right
Result: 2, 7, 5, 6, 11, 1, 9, 5, 9

Question 13

Pre-order traversal

Answer 13

Root -> Left -> Right
Result: 1, 7, 2, 6, 5, 11, 9, 9, 5

Question 14

Post-order traversal

Answer 14

Left -> Right -> Root
Result: 2, 5, 11, 6, 7, 5, 9, 9, 1

Question 15

Binary search tree (BST)

Answer 15

In-order traversal of a BST will give you all elements in order.

Question 16

Operation Big-O
Access
Search
Insert
Remove

Answer 16

Operation Big-O
Access O(log(n))
Search O(log(n))
Insert O(log(n))
Remove O(log(n))