Data Structures and Algorithms · Unit 8
Trees and Binary Search Trees
Exam-focused notes for Trees and Binary Search Trees (Data Structures and Algorithms, BIT201): what the TU syllabus asks and how it has actually been tested, with 9 solved past questions from this unit.
What this unit covers
- Binary tree definition and applications
- Complete binary tree definition with examples
- Almost complete binary tree definition with examples
- Binary search tree (BST) definition
- BST search algorithm
- BST insertion algorithm
- BST deletion algorithm
- Pre-order traversal method
- In-order traversal method
- Post-order traversal method
- Binary tree traversal examples
Pre-order traversal method
Traverse the following tree in pre-order and in-order. [5]
Task: Traverse a given tree in pre-order and in-order. Tree structure: The tree diagram/image is NOT provided in the question. Only the instruction and the mark allocation ([5]) are given. Missing data: The actual tree (nodes and their parent/child relation...
Full solved answer →What are the different traversing methods in a binary tree? Explain with a clear example. [5]
Tree traversal means visiting every node in a binary tree exactly once in a specific order. There are three standard depth-first traversal methods plus level-order traversal. --- For any node, the traversal involves three actions: - L = Visit Left subtree -...
Full solved answer →Binary tree definition and applications
Define binary tree and binary search tree. List the applications of Binary tree. [2+3]
--- A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. Formal Definition: A binary tree is either: - An empty tree (null), OR - A node consisting of a root, a left subtree, ...
Full solved answer →What are different applications of binary tree? Explain. [5]
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. Binary trees have numerous important applications in computer science. --- - A binary tree is used to implement BST, where...
Full solved answer →Explain different applications of binary tree. [5]
--- A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. Binary trees have numerous important applications in computer science. --- - A binary tree is used to implement BST, w...
Full solved answer →What is binary tree? Explain different application of binary tree. [5]
A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. A binary tree consists of: - Root node - the topmost node of the tree - Left subtree - a binary tree on the left side - Ri...
Full solved answer →Almost complete binary tree definition with examples
Explain almost complete binary tree with example. How do you insert, search, and delete nodes in a binary search tree? Explain with suitable example?[10]
--- An Almost Complete Binary Tree (also called a Nearly Complete Binary Tree) is a binary tree in which: - All levels are completely filled except possibly the last level. - The last level has all nodes as far left as possible. This is the structural prope...
Full solved answer →Complete binary tree definition with examples
Explain complete binary tree with example. Starting with an empty binary search tree, show the effect of successively adding the following elements: 47, 50, 25, 27, 17, 61, 5, and 26. Also, traverse the resulting tree in pre-order, in-order, and post-order.[5]
- Insertion sequence into an empty BST: 47, 50, 25, 27, 17, 61, 5, 26 - Required: definition + example of complete binary tree, BST construction, and pre-order, in-order, post-order traversals. All data present. --- A complete binary tree is a binary tree i...
Full solved answer →BST search algorithm
What is a Binary Search Tree? Write an algorithm for searching an item in a binary search tree. [5]
A Binary Search Tree (BST) is a binary tree data structure in which each node contains a key (value), and the following properties hold for every node: 1. The left subtree of a node contains only nodes with keys less than the node's key. 2. The right subtre...
Full solved answer →Make Unit 8 stick
Practice BIT201 with flashcards & quizzes