Week 3 - Tree Structure Flashcards
How is insertion done efficiently in a tree structure (e.g., Binary Search Tree)?
To insert an element:
- Start from the root.
- Recursively compare the new value with the current node.
- Move left if smaller, right if larger.
- Insert the new node at the appropriate null (leaf) position.
Time Complexity: O(log n) for a balanced tree, O(n) in the worst case (unbalanced tree).
How is deletion handled efficiently in a Binary Search Tree?
To delete a node:
- Find the node to be deleted.
- Three cases:
- No children: Simply remove the node.
- One child: Replace the node with its child.
- Two children: Replace the node with its in-order successor or predecessor, then delete the successor/predecessor.
Time Complexity: O(log n) for balanced trees, O(n) in the worst case.
What is a Tree in data structures?
A Tree is a non-linear data structure that simulates a hierarchical structure with a set of connected nodes. It has:
A single root node.
No loops (i.e., it’s acyclic).
What are the basic components (terminologies) of a tree?
Nodes: Individual elements of the tree.
Edges: Connections between nodes.
Leaves: Nodes with no children.
Height/Depth: The longest path from the root to any leaf node.
What is the root in a tree data structure?
The root is the topmost node in a tree. It is the starting point from which all other nodes branch out.
What is the height of a tree?
The height of a tree is the number of edges on the longest path from the root to any leaf node.
What is a Binary Tree?
A Binary Tree is a tree data structure where each node has at most two children, commonly referred to as the **left
What is a Binary Search Tree (BST)?
A Binary Search Tree is a binary tree where:
The left child of a node contains only nodes with values less than the node’s value.
The right child contains only nodes with values greater than the node’s value.
This ordering property makes search operations efficient.
What is a Balanced Tree?
A Balanced Tree is a binary tree in which the height difference between the left and right subtrees of any node is no more than one. This ensures performance remains optimal.
Why is balancing important in binary search trees?
Balancing avoids skewed structures (like linked lists), maintaining O(log n) efficiency for operations like search, insert, and delete.
What happens when a Binary Search Tree is not balanced?
If a BST becomes unbalanced (e.g., all nodes inserted in sorted order), it can degrade to a linked list, causing operations to take O(n) time.
What is the representation of an empty binary tree?
An empty tree is represented as either:
Empty or a blank tree ()
How do you build a binary tree using the expression Fork(X, L, R)?
You create a binary tree with:
X as the current node (label)
L as the left subtree
R as the right subtree
Example: Fork(3, Empty, Empty) represents a single-node tree with value 3.
What are the only two components needed to build all binary trees?
All binary trees can be built using only:
Empty (to represent no node)
Fork (to combine nodes and subtrees)
