Non-Linear Data Structures: Trees: 31 flashcards
All 31 flashcards from this kit, free and with no sign-up.
1. Why is a tree called a non-linear data structure?
Show the answer
Because one node can connect to many children (one-to-many), unlike arrays or lists where each element has at most one predecessor and one successor.
2. What is the root of a tree?
Show the answer
The topmost node of the tree — the only node with no parent.
3. What is a leaf node?
Show the answer
A node with no children (degree 0).
4. Define the degree of a node.
Show the answer
The number of children that node has.
5. Define the depth of a node.
Show the answer
The number of edges from the root down to that node.
6. Define the height of a tree.
Show the answer
The maximum depth among all nodes in the tree.
7. What is a subtree?
Show the answer
Any node together with all of its descendants — a tree inside a tree.
8. How many edges does a tree with n nodes have?
Show the answer
Exactly n − 1 edges.
9. What is a forest?
Show the answer
A collection of disjoint trees.
10. What is a binary tree?
Show the answer
A tree in which every node has at most two children, called the left child and right child.
11. State the binary search tree (BST) ordering property.
Show the answer
For every node, all values in its left subtree are smaller and all values in its right subtree are larger than the node's value.
12. What is the search time in a balanced BST?
Show the answer
$O(\log n)$ — each comparison discards about half the remaining tree.
13. What is the search time in an unbalanced (degenerate) BST?
Show the answer
$O(n)$ — the tree behaves like a linked list.
14. Describe preorder traversal.
Show the answer
Visit the node, then the left subtree, then the right subtree (root first).
15. Describe inorder traversal.
Show the answer
Visit the left subtree, then the node, then the right subtree. On a BST it yields sorted order.
16. Describe postorder traversal.
Show the answer
Visit the left subtree, then the right subtree, then the node (children before parent).
17. Describe level-order traversal.
Show the answer
Visit nodes level by level from top to bottom, using a queue.
18. Which traversal of a BST gives sorted output?
Show the answer
Inorder traversal.
19. Which traversal is used to safely delete a tree?
Show the answer
Postorder — children are processed before their parent.
20. Which traversal is used to copy a tree?
Show the answer
Preorder — the parent is created before its children.
21. Name three real-world uses of trees.
Show the answer
File systems, the HTML DOM, database indexes (B-trees/B+ trees), and compiler syntax trees.
22. What structure do database indexes commonly use?
Show the answer
B-trees or B+ trees.
23. How is a tree related to a graph?
Show the answer
A tree is a special graph: connected and acyclic. Not every graph is a tree.
24. What happens if you add an edge that creates a second path between two nodes?
Show the answer
You create a cycle, and the structure is no longer a tree.
25. What happens when sorted input is inserted into a naive BST?
Show the answer
The tree degenerates into a linked-list-like structure and search drops to $O(n)$.
26. What is the difference between a binary tree and a BST?
Show the answer
A binary tree only limits each node to two children; a BST also enforces left-smaller / right-larger ordering.
27. What is the parent of a node?
Show the answer
The node directly above it in the tree.
28. What is the degree of a leaf node?
Show the answer
Zero — it has no children.
29. What is the depth of the root node?
Show the answer
Zero — there are no edges above it.
30. Why do real systems use self-balancing trees instead of naive BSTs?
Show the answer
To keep height near $\log n$ and preserve fast $O(\log n)$ search even with adversarial or sorted input.
31. What does a compiler build from source code?
Show the answer
A syntax tree.
Your notes can be a kit like these
Every kit here was made from real study material. Point Veda at a chapter, a PDF, a photo or a link and get notes, flashcards, practice MCQs, games and a scored test — free, in 42 languages.
- Chapter notes
- Flashcards
- Practice MCQs
- Scored tests
- Exam prep
Get Veda free See what students get
Free to start · No ads · Works in 42 languages