Module 4

Question 1

STANDS AS A PIVOTAL NONLINEAR DATA STRUCTURE

IS EITHER EMPTY OR CONSISTS OF A ROOT NODE AND ZERO OR MORE SUBTREES.

Answer 1

Tree

Question 2

Type of Trees

Answer 2

• ORDERED TREE
• ORIENTED TREE
• FREE TREE

Question 3

FINITE SET OF NODES WHERE ONE IS THE ROOT AND THE REST ARE PARTITIONED INTO ORDERED SUBTREES, PRESERVING THE SIGNIFICANCE OF NODE ORDER.

Answer 3

ORDERED TREE

Question 4

A TREE WHERE THE ORDER OF SUBTREES FOR EACH NODE DOESN’T HOLD SIGNIFICANCE.

Answer 4

ORIENTED TREE

Question 5

HAS NO NODE DESIGNATED AS THE ROOT AND THE ORIENTATION FROM A NODE TO ANY OTHER NODE IS INSIGNIFICANT.

Answer 5

FREE TREE

Question 6

A FREE TREE WITH A DESIGNATED ROOT TRANSFORMS INTO AN ORIENTED TREE

WHEN A FREE TREE IS DESIGNATED A ROOT NODE, IT BECOMES AN ORIENTED TREE. WHEN THE ORDER OF THE NODES ARE DEFINED IN AN ORIENTED TREE, IT BECOMES AN ORDERED TREE.

Answer 6

Tree Progression

Question 7

Types of Representations

Answer 7

Link Representations
Binary Representations

Question 8

o UTILIZES LINKS TO DEPICT TREE STRUCTURES, WHERE EACH NODE CONTAINS LINKS TO ITS POSSIBLE SONS.

Answer 8

Link Representations

Question 9

o AN ALTERNATIVE STRUCTURE, PRIMARILY FOR BINARY TREES, USING LEFT AND RIGHT POINTERS TO DESIGNATE THE LEFTMOST SON AND THE NEXT YOUNGER BROTHER

Answer 9

Binary Representations

Question 10

• ASSEMBLING DISJOINT TREES FORMS A _______
• WHEN ZERO OR MORE DISJOINT TREES ARE TAKEN TOGETHER, THEY ARE KNOWN AS A ______.

Answer 10

Forest

Question 11

• A PROCESS CONVERTING AN ORDERED FOREST INTO A UNIQUE BINARY TREE AND VICE VERSA USING A SPECIFIC METHOD,

Answer 11

Natural Correspondence

Question 12

A HIERARCHICAL DATA STRUCTURE CONSISTING OF NODES ORGANIZED IN A SPECIFIC ARRANGEMENT

Answer 12

Binary Tree Structure

Question 13

Binary Tree Structure KEY CHARACTERISTICS ARE

Answer 13

o NODES
o ROOTS NODES
o CHILD NODES
o LEAVES OR TERMINAL NODE
o INTERNAL NODE

Question 14

CONTAINS:
o DATA OR PAYLOAD.
o REFERENCES OR POINTERS TO AT MOST TWO CHILD NODES, TYPICALLY DENOTED AS THE LEFT CHILD AND THE RIGHT CHILD.
IN A BINARY TREE CAN HAVE ZERO, ONE, OR TWO CHILDREN.

Answer 14

Node

Question 15

• THE TOPMOST NODE OF THE TREE.
• IT SERVES AS THE STARTING POINT FOR ACCESSING ALL OTHER NODES IN THE TREE.

Answer 15

Root Node

Question 16

• EVERY NODE (EXCEPT THE LEAVES) HAS AT MOST TWO CHILDREN - A LEFT CHILD AND A RIGHT CHILD.
• THESE ______ ARE CONNECTED DOWNWARDS FROM THEIR PARENT NODE.

Answer 16

Chilld Node

Question 17

• NODES WITHOUT ANY CHILDREN ARE TERMED AS _________.

Answer 17

LEAVES OR TERMINAL NODES

Question 18

• NODES THAT HAVE AT LEAST ONE CHILD ARE CONSIDERED _________.

Answer 18

INTERNAL NODES

Question 19

Node Relationships in a Binary Tree

Answer 19

Root Node
Parent and Children Nodes
Leaves or Terminal Nodes
Internal Nodes
Siblings
Ancestors and Descendants

Question 20

• THE TOPMOST NODE IN THE BINARY TREE.
• DOES NOT HAVE A PARENT NODE AND SERVES AS THE STARTING POINT FOR TRAVERSING THE TREE.

Answer 20

Root Node

Question 21

• EACH NODE (EXCEPT THE ROOT) HAS A PARENT NODE.
• NODES MAY HAVE AT MOST TWO CHILDREN, KNOWN AS THE LEFT CHILD AND THE RIGHT CHILD.

Answer 21

Parent and Children Nodes

Question 22

• NODES WITHOUT CHILDREN ARE THE __________.
• THEY DO NOT HAVE ANY FURTHER DESCENDANTS.

Answer 22

Leaves or Terminal Node

Question 23

• NODES WITH AT LEAST ONE CHILD ARE _______.
• THEY SERVE AS INTERMEDIARIES BETWEEN THE ROOT AND THE LEAVES.

Answer 23

Internal Nodes

Question 24

• NODES THAT SHARE THE SAME PARENT ARE CALLED __________.
• THEY ARE ON THE SAME LEVEL OF THE TREE AND HAVE THE SAME PARENT NODE.

Answer 24

Siblings

Question 25

* _________ OF A NODE ARE ALL THE NODES PRESENT ON THE PATH FROM THE ROOT TO THAT PARTICULAR NODE. * ____________ OF A NODE ARE ALL THE NODES REACHABLE FROM THAT NODE, INCLUDING ITS CHILDREN, GRANDCHILDREN, AND SO FORTH.

Answer 25

Ancestors and Descendants

Question 26

Types of Binary Trees

Answer 26

Skewed Binary Tree Strict Binary Tree Full Binary Tree

Question 27

o EVERY NODE HAS NO LEFT (RIGHT) SUBTREE, CREATING A LINEAR STRUCTURE.

Answer 27

Skewed Binary Tree

Question 28

* EACH NODE EITHER HAS TWO CHILDREN OR NONE AT ALL

Answer 28

Strict Binary Tree

Question 29

* EVERY INTERNAL NODE HAS EXACTLY TWO CHILDREN.

Answer 29

Full Binary Tree

Question 30

Complete Binary Tree * CONSTRUCTED BY SYSTEMATICALLY DELETING NODES FROM A FULL BINARY TREE IN A SPECIFIC ORDER (RIGHT TO LEFT, BOTTOM TO TOP).

Answer 30

Complete Binary Tree

Question 31

Properties of Binary Trees

Answer 31

Level and Height Internal and External Nodes Number of Nodes Terminal Nodes

Question 32

o NODES' DISTANCE FROM THE ROOT. THE ROOT IS AT LEVEL 0, AND EACH LEVEL MOVES FURTHER AWAY FROM THE ROOT.

Answer 32

Level

Question 33

o THE LENGTH OF THE LONGEST ROOT-TO-LEAF PATH. IT SIGNIFIES THE MAXIMUM DEPTH OF THE TREE.

Answer 33

Height

Question 34

o NODES WITH AT LEAST ONE CHILD.

Answer 34

Internal Node

Question 35

o NODES WITHOUT CHILDREN, ALSO KNOWS AS TERMINAL OR LEAF NODES.

Answer 35

External Node

Question 36

* THE MAXIMUM NUMBER OF NODES FOR A DEPTH OF K IS 2^K - 1, AND THE MINIMUM NUMBER IS 2^K+1 – 1.

Answer 36

Number of nodes

Question 37

* THE COUNT OF ______ (N0) OR LEAVES IN RELATION TO NODES WITH DEGREE 2 (N2) IS GIVEN BY N0 = N2 + 1. * THIS RELATION HOLDS IN ANY BINARY TREE, WHERE THE NUMBER OF LEAVES IS ONE MORE THAN THE NUMBER OF NODES WITH EXACTLY TWO CHILDREN.

Answer 37

Terminal Nodes

Question 38

* IS THE PROCESS OF VISITING AND PROCESSING EACH NODE IN A BINARY TREE IN A SYSTEMATIC ORDER.

Answer 38

Binary Tree Traversal

Question 39

(Root -> Left -> Right)

Answer 39

Pre-Order Traversal

Question 40

(Left -> Root -> Right)

Answer 40

In-Order Traversal

Question 41

( Left -> Right -> Root).

Answer 41

Post-Order Traversal

Question 42

Advance Concepts and Variants

Answer 42

Self-Balancing Binary Tree Binary Heaps

Question 43

* Red-Black Trees, AVL Trees o TREES THAT AUTOMATICALLY BALANCE THEMSELVES, ENSURING OPTIMAL PERFORMANCE FOR OPERATIONS LIKE INSERTION, DELETION, AND SEARCH.

Answer 43

Self-Balancing Binary Tree

Question 44

* Mini-Heap, Max-Heaps o SPECIALIZED BINARY TREES USED FOR PRIORITY QUEUES, ENSURING EFFICIENT ACCESS TO HE MINIMUM OR MAXIMUM ELEMENT.

Answer 44

Binary Heaps

Question 45

* IS A FUNDAMENTAL DATA STRUCTURE IN COMPUTER SCIENCE THAT ORGANIZES NODES IN A HIERARCHICAL STRUCTURE.

Answer 45

Binary Search Trees

Question 46

Operation on Binary Search Trees

Answer 46

Searching Insertion Deletion

Question 47

* THE SEARCH OPERATION IN A BST (BINARY SEARCH TREE) INVOLVES COMPARING THE VALUE TO BE FOUND WITH THE VALUE AT THE CURRENT NODE

Answer 47

Searching

Question 48

* WHEN INSERTING A NEW NODE INTO A BST * START WITH A SEARCH TO FIND THE APPROPRIATE LOCATION FOR THE NEW NODE. * IF THE SEARCH REACHES A NULL POSITION, INSERT THE NEW NODE WITH THE VALUE 'K' AT THAT POSITION ACCORDING TO THE BST PROPERTY.

Answer 48

Insertion

Question 49

* DELETING A NODE IN A BST REQUIRES CAREFUL HANDLING TO MAINTAIN THE TREE'S BST PROPERTY: * IF THE NODE TO BE DELETED IS A LEAF NODE (NO CHILDREN), SIMPLY REMOVE IT BY UPDATING ITS PARENT'S POINTER. * IF THE NODE HAS ONLY ONE CHILD, REPLACE THE NODE TO BE DELETED WITH ITS CHILD. * IF THE NODE HAS TWO CHILDREN: * FIND EITHER ITS IN-ORDER PREDECESSOR OR SUCCESSOR. * REPLACE THE NODE TO BE DELETED WITH THE PREDECESSOR OR SUCCESSOR. * ADJUST THE POINTERS TO MAINTAIN THE BST PROPERTY.

Answer 49

Deletion

Question 50

- HAPPENS WHEN THE TREE IS BALANCED.

Answer 50

* AVERAGE CASE: O(LOG₂ N)

Question 51

OCCURS WHEN THE TREE IS DEGENERATE (SKEWED, ALL NODES TO ONE SIDE).

Answer 51

* WORST CASE: O(N)

Question 52

* SIMILAR TO SEARCH, THESE OPERATIONS HAVE O(LOG₂ N) TIME COMPLEXITY ON AVERAGE BUT CAN DETERIORATE TO O(N) IN A DEGENERATE TREE.

Answer 52

Insertion and Deletion

Question 53

* MAINTAIN O(LOG₂ N) TIME FOR SEARCH, INSERTION, AND DELETION.

Answer 53

BALANCED BSTS

Question 54

* PERFORM SIMILAR TO A LINKED LIST WITH O(N) TIME COMPLEXITY FOR SEARCH, MAKING THEM LESS EFFICIENT.

Answer 54

UNBALANCED (DEGENERATE) BSTS

Question 55

* ARE A FUNDAMENTAL TYPE OF SELF-BALANCING BINARY SEARCH TREE NAMED AFTER THEIR INVENTORS, ADELSON-VELSKY AND LANDIS.

Answer 55

AVL trees

Question 56

Characteristics of AVL Trees

Answer 56

Balance Factor Balancing Conditions

Question 57

* EACH NODE IN AN AVL TREE HAS A BALANCE FACTOR, WHICH IS THE DIFFERENCE IN HEIGHT BETWEEN THE LEFT AND RIGHT SUBTREES.

Answer 57

Balance Factor

Question 58

* FOR ANY NODE IN THE AVL TREE, THE HEIGHT DIFFERENCE (BALANCE FACTOR) BETWEEN ITS LEFT AND RIGHT SUBTREES SHOULD NOT EXCEED 1. * THIS CONDITION HOLDS TRUE FOR EVERY NODE IN THE TREE.

Answer 58

Balancing Conditions

Question 59

Operations in AVL Trees

Answer 59

Insertion Deletion

Question 60

* WHEN A NEW NODE IS INSERTED INTO AN AVL TREE, THE TREE MIGHT BECOME UNBALANCED. * AFTER INSERTION, THE BALANCE FACTORS OF NODES ALONG THE INSERTION PATH ARE UPDATED. * IF THE BALANCE CONDITION IS VIOLATED, ROTATIONS (SINGLE OR DOUBLE) ARE PERFORMED TO RESTORE BALANCE WHILE MAINTAINING THE ORDERING PROPERTY OF THE BST.

Answer 60

Insertion

Question 61

* DELETING A NODE MAY ALSO LEAD TO AN IMBALANCE IN THE AVL TREE. * SIMILAR TO INSERTION, AFTER DELETION, THE BALANCE FACTORS OF AFFECTED NODES ARE UPDATED. * IF NECESSARY, ROTATIONS ARE PERFORMED TO RESTORE BALANCE.

Answer 61

Deletion

Question 62

Rotations In AVL Trees

Answer 62

Single Rotations Double Rotations

Question 63

* LEFT ROTATION: * RIGHT ROTATION:

Answer 63

Single Rotations

Question 64

* LEFT-RIGHT ROTATION * RIGHT-LEFT ROTATION

Answer 64

Double Rotations