2.5 Trees

• What is a tree in computer science terms?

  Non-linear data structure
• The top-most node of a tree is called the root
• Leaf nodes in a tree have no children.
• What is the primary property of a binary tree?

  Each node has at most two children
• In a binary search tree (BST), all values in the left subtree are smaller than the root
• What is the key feature of a balanced tree like an AVL tree?

  The heights of left and right subtrees differ by at most one
• In a full binary tree, each node has either 0 or 2 children.
• What is the defining characteristic of a complete binary tree?

  All levels are completely filled except possibly the deepest level
• Steps of in-order tree traversal

  1️⃣ Visit the left subtree

  2️⃣ Visit the root

  3️⃣ Visit the right subtree
• Match the tree traversal method with its order of visits:

  In-order ↔️ Left Subtree → Root → Right Subtree

  Pre-order ↔️ Root → Left Subtree → Right Subtree

  Post-order ↔️ Left Subtree → Right Subtree → Root
• Pre-order traversal is often used to serialize trees.
• What is the primary goal of tree traversal?

  Visit each node once
• Inorder traversal visits nodes in the order: left subtree, current node, right subtree
• What is the traversal order for preorder traversal?

  Current, left, right
• Arrange the traversal methods in order based on when the current node is visited.

  1️⃣ Preorder

  2️⃣ Inorder

  3️⃣ Postorder
• In postorder traversal, the current node is visited after the left and right subtrees
• The inorder traversal for the tree \begin{array}{c} 1 \\\downarrow\hspace{1.5cm}\downarrow \\ 2 \hspace{1.5cm} 3 \\\downarrow\hspace{1.5cm}\downarrow \\ 4 \hspace{1.5cm} 5 \end{array}</latex> is $4, 2, 5, 1, 3$
• A subtree is a part of the tree that is also a tree
• What is a tree in computer science terms?

  A non-linear data structure
• The top-most node of a tree is called the root
• A child node in a tree is directly connected below another node.
• What is the node above another node called?

  Parent
• In a binary tree, each node can have at most two children.
• Match the type of tree with its property:

  Binary Search Tree ↔️ Efficient searching due to ordered structure

  Balanced Tree ↔️ $O(\log n)$ operations on average
• Why is a Binary Search Tree (BST) efficient for searching?

  Ordered structure
• A B-Tree allows nodes to have more than two children.
• In a full binary tree, each node has either 0 or two children.
• What is a complete binary tree?

  All levels are filled except possibly the deepest
• Arrange the types of binary trees in order of their structural complexity:

  1️⃣ Full Binary Tree

  2️⃣ Complete Binary Tree

  3️⃣ Perfect Binary Tree
• What is a binary tree?

  A hierarchical data structure
• In a full binary tree, each node has either 0 or 2
• What is a complete binary tree?

  All levels filled except deepest
• In a perfect binary tree, all internal nodes have 2 children.
• What is the defining property of a full binary tree?

  Each node has 0 or 2 children
• Order the three primary methods of tree traversal

  1️⃣ Inorder

  2️⃣ Preorder

  3️⃣ Postorder
• Tree traversal involves visiting each node in a tree data structure exactly once.
• What is the traversal order in an inorder traversal?

  Left subtree, current node, right subtree
• What is the traversal order in a preorder traversal?

  Current node, left subtree, right subtree
• What does tree traversal involve in data structures?

  Visiting each node once
• Match the tree traversal method with its description:

  Inorder ↔️ Left subtree, current node, right subtree

  Preorder ↔️ Current node, left subtree, right subtree

  Postorder ↔️ Left subtree, right subtree, current node