Trees

Question 1

Define binary tree.

Answer 1

A tree data structure where each node has at most two children.

Question 2

What is the height of a tree?

Answer 2

The length of the longest path from the root to a leaf.

Question 3

True or false: A leaf node has no children.

Answer 3

TRUE

Question 4

Fill in the blank: A full binary tree has ______ children per node.

Answer 4

Two

Question 5

What does in-order traversal do?

Answer 5

Visits nodes in the left subtree, then the root, then the right subtree.

Question 6

Define balanced tree.

Answer 6

A tree where the height of the left and right subtrees differ by at most one.

Question 7

What is a leaf in a tree?

Answer 7

A node with no children.

Question 8

True or false: A binary search tree allows duplicate values.

Answer 8

FALSE

Question 9

What is the root of a tree?

Answer 9

The topmost node in a tree structure.

Question 10

Fill in the blank: A complete binary tree is fully filled on all levels except ______.

Answer 10

The last level

Question 11

Define traversal in trees.

Answer 11

The process of visiting all the nodes in a tree.

Question 12

What is a sibling in a tree?

Answer 12

Nodes that share the same parent.

Question 13

True or false: A binary tree can be unbalanced.

Answer 13

TRUE

Question 14

What is the depth of a node?

Answer 14

The number of edges from the tree’s root to the node.

Question 15

Fill in the blank: The maximum number of nodes at level ‘n’ is ______.

Answer 15

2^n

Question 16

Define pre-order traversal.

Answer 16

Visits the root node first, then the left subtree, then the right subtree.

Question 17

What is a binary heap?

Answer 17

A complete binary tree that satisfies the heap property.

Question 18

True or false: A tree can have cycles.

Answer 18

FALSE

Question 19

What is the degree of a node?

Answer 19

The number of children a node has.

Question 20

Fill in the blank: A trie is a type of tree used for ______.

Answer 20

Storing strings

Question 21

Define post-order traversal.

Answer 21

Visits the left subtree, then the right subtree, then the root node.

Question 22

What is a subtree?

Answer 22

A tree formed by a node and its descendants.

Question 23

True or false: Trees can be used to implement priority queues.

Answer 23

TRUE

Question 24

What is the level of a node?

Answer 24

The number of edges on the path from the root to the node.

Question 25

Fill in the blank: A **red-black tree** is a type of ______.

Answer 25

Self-balancing binary search tree

Question 26

Define **B-tree**.

Answer 26

A self-balancing tree data structure that maintains sorted data.

Question 27

What is the **order** of a B-tree?

Answer 27

The maximum number of children a node can have.

Question 28

الجذر (Root):

Answer 28

أول عقدة تبدأ منها الشجرة، ولا يوجد عقدة أب لها.

Question 29

الحافة (Edge):

Answer 29

الخط الواصل بين عقدتين.

Question 30

الأب/الوالد (Parent):

Answer 30

العقدة التي لها أبناء.

Question 31

الابن (Child):

Answer 31

كل عقدة منبثقة من عقدة أخرى.

Question 32

الأشقاء (Siblings):

Answer 32

عقد لها نفس الوالد.

Question 33

الدرجة (Degree):

Answer 33

عدد أبناء العقدة؛ أما درجة الشجرة فهي أكبر درجة بين كل عقد.

Question 34

العقدة الداخلية (Internal node):

Answer 34

عقدة لها ابن واحد على الأقل.

Question 35

عقدة ورقية (Leaf node):

Answer 35

عقدة بلا أبناء.

Question 36

المستوى (Level):

Answer 36

المسافة من الجذر للعقدة (تبدأ من 0).

Question 37

الارتفاع (Height):

Answer 37

أطول مسار من العقدة حتى أبعد عقدة ورقية تحتها.

Question 38

العمق (Depth):

Answer 38

عدد الحواف من الجذر للعقدة.

Question 39

الشجرة الفرعية (Subtree):

Answer 39

كل ابن يشكل مع أبناءه شجرة فرعية.

Question 41

What is a **Full Binary Tree**?

Answer 41

A Binary Tree where every node has 0 or 2 children ## Footnote All nodes except leaf nodes have two children.

Question 42

What defines a **Complete Binary Tree**?

Answer 42

All levels are completely filled except possibly the last level, which has all keys as left as possible ## Footnote Examples include trees where the last level is filled from left to right.

Question 43

What is a **Perfect Binary Tree**?

Answer 43

A Binary Tree where all internal nodes have two children and all leaf nodes are at the same level ## Footnote This structure ensures maximum efficiency in tree operations.

Question 44

In a **Binary Search Tree**, the value of the left node must be ______ the parent node.

Answer 44

smaller ## Footnote Conversely, the value of the right node must be greater than the parent node.

Question 45

What are the steps for **creating a Binary Search Tree**?

Answer 45

* Insert root * Compare and place left or right based on value * Repeat for each element ## Footnote The example provided illustrates the insertion of specific values into the tree.

Question 46

What are the steps for **searching in a Binary Search Tree**?

Answer 46

* Compare with root * Move left if smaller * Move right if larger * Repeat until found or return NULL ## Footnote This method leverages the ordered structure of BSTs for efficient searching.

Question 47

What are the three possible situations for **deleting a node** in a Binary Search Tree?

Answer 47

* Leaf node: Remove it * One child: Replace with child * Two children: Replace with in-order successor/predecessor ## Footnote Each situation requires a different approach to maintain the BST properties.

Question 48

What are the three main ways to **traverse a binary tree**?

Answer 48

* Pre-Order (Root -> Left -> Right) * In-Order (Left -> Root -> Right) * Post-Order (Left -> Right -> Root) ## Footnote Each traversal method serves different purposes, especially in BSTs.

Question 49

In **In-Order Traversal** of a BST, what order do the nodes appear?

Answer 49

Ascending order ## Footnote This traversal method visits the left subtree, the root, and then the right subtree.