Binary Tree Properties Quiz

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

In a binary sorted tree, what type of elements does the left subtree of a node contain?

  • Elements greater than the node element
  • Elements less than or equals to the node element (correct)
  • Elements equals to the node element
  • Elements greater than or equals to the node element

When searching for a target element in a binary sorted tree, if the target is less than or equals to the node element, where should the search go?

  • Down the left subtree (correct)
  • Move to the parent node
  • Down the right subtree
  • Stay at the current node

What does the BSTree Java class constructor with no parameters do?

  • Creates a binary sorted tree with a single node
  • Constructs an empty binary sorted tree (correct)
  • Throws an exception
  • Initializes the root node with a null element

What does the BSTreeNode Java class represent?

<p>Nodes in a binary sorted tree (C)</p> Signup and view all the answers

What defines a balanced binary tree?

<p>The height difference between the left and right subtrees of every node is at most 1 (A)</p> Signup and view all the answers

How is the maximum number of nodes for a binary tree of height 1 determined?

<p>3 (D)</p> Signup and view all the answers

What characterizes a proper binary tree?

<p>Each node has either 0 or 2 children (A)</p> Signup and view all the answers

What is the height of a balanced binary tree of size n?

<p>$\lfloor \log_2 n \rfloor + 1$ (D)</p> Signup and view all the answers

In heap insertion, when adding a new node to the lowest point in the tree, what is the next step after placing the new node?

<p>Upheap node values to its rightful place in the tree (A)</p> Signup and view all the answers

In heap deletion, what is the condition for swapping a child node with the new node in a max heap?

<p>If child node is greater than the new node (B)</p> Signup and view all the answers

What type of deletion is allowed in a heap data structure?

<p>Restricted deletion called extraction (B)</p> Signup and view all the answers

What is the time complexity of a well-balanced tree for insertion and deletion operations?

<p>O(log n) (A)</p> Signup and view all the answers

How does each insertion and deletion operation affect the balance of a tree?

<p>They affect the balance of the tree (D)</p> Signup and view all the answers

What is the objective in maintaining the balance of a tree after each operation?

<p>To keep the height of the tree to a minimum (D)</p> Signup and view all the answers

What does the balance of a node in a tree represent?

<p>The height of the right sub-tree minus the height of the left sub-tree (A)</p> Signup and view all the answers

How is the balance of a node calculated in a tree?

<p>Balance(n) = right-height(n) - left-height(n) (D)</p> Signup and view all the answers

In a balanced binary tree, what is the relationship between the heights of the left and right sub-trees of a node?

<p>The heights are such that the absolute difference is at most 1 (B)</p> Signup and view all the answers

What is the maximum number of nodes and elements on level 3 of a B-Tree of order 100?

<p>Nodes: 202, Elements: 40,401 (A)</p> Signup and view all the answers

What variant of B-Tree facilitates sequential access of a file by having pointers in leaf nodes to the next sibling?

<p>B+Tree (C)</p> Signup and view all the answers

What percentage of fullness do B*Trees operate at on average?

<p>81% (D)</p> Signup and view all the answers

In a B-Tree of order 2, what is the resulting tree after adding the sequence: 80, 20, 60, 40, 30, 90, 35, 50, 10, 15, 31, 5, 23, 18, 22, 12, 95?

<p>The resulting B-Tree after adding the given sequence (B)</p> Signup and view all the answers

When does a node in a B-tree need to split into 2 nodes?

<p>When it has more than 2n elements (D)</p> Signup and view all the answers

What happens when a node in a B-tree becomes full?

<p>It must split into 2 nodes (D)</p> Signup and view all the answers

What happens when a new element needs to be added to a full B-tree with a full root node?

<p>The root node is split and a new root node is created (D)</p> Signup and view all the answers

What is the objective in maintaining the balance of a binary tree?

<p>To optimize search and insertion operations (D)</p> Signup and view all the answers

What is the purpose of B-trees in the context of hierarchical abstract data types?

<p>Efficiently handle large amounts of data and minimize disk access (A)</p> Signup and view all the answers

When discussing hierarchical abstract data types, what does a balanced binary tree aim to achieve?

<p>Minimize the height disparity between left and right subtrees (A)</p> Signup and view all the answers

How is the size of a tree defined?

<p>The total number of nodes (C)</p> Signup and view all the answers

What is a characteristic of a node in a tree?

<p>A node must have only one unique path from the root (C)</p> Signup and view all the answers

What does the height of a tree represent?

<p>The number of levels with nodes (C)</p> Signup and view all the answers

What forms the left and right subtrees in a binary tree?

<p>Left child and its descendants for the left subtree, right child and its descendants for the right subtree (B)</p> Signup and view all the answers

What is the maximum number of children a node can have in a binary tree?

<p>2 (A)</p> Signup and view all the answers

What characterizes a complete binary tree of height h?

<p>It is full to level (h-1) and has level h filled from left to right (B)</p> Signup and view all the answers

What characterizes a full binary tree of height h?

<p>All leaves are at level h and all other nodes each have 2 children (C)</p> Signup and view all the answers

In a binary tree, what characterizes a node at level h-1 in a complete binary tree?

<p>Each node has 2 children (D)</p> Signup and view all the answers

What is the maximum height of an ill-balanced tree of size n?

<p>n (B)</p> Signup and view all the answers

How will an ill-balanced binary tree perform?

<p>Like a linear data structure (B)</p> Signup and view all the answers

What is the minimum number of nodes a balanced binary tree of height 4 can have?

<p>8 (D)</p> Signup and view all the answers

What is the maximum height of a balanced binary tree with 63 nodes?

<p>6 (A)</p> Signup and view all the answers

How many nodes can a balanced binary tree of height 6 have at most?

<p>127 (B)</p> Signup and view all the answers

What is the minimum number of nodes a balanced binary tree of height h has?

<p>2^(h-1) (B)</p> Signup and view all the answers

What is the formula to calculate the height of a balanced binary tree of size n?

<p>log2(n) + 1 (D)</p> Signup and view all the answers

What is the maximum number of nodes a balanced binary tree of height h can have?

<p>2^h - 1 (C)</p> Signup and view all the answers

What is the time complexity for searching, sorting, insertion, and deletion operations in a balanced binary tree?

<p>O(log n) (A)</p> Signup and view all the answers

What is the time complexity for accessing any node in an ill-balanced binary tree?

<p>O(n) (B)</p> Signup and view all the answers

What kind of elements does the left subtree of a node in a binary sorted tree contain?

<p>Elements less than or equals to the node element (D)</p> Signup and view all the answers

What does a node in the right subtree of a node in a binary sorted tree contain?

<p>Elements greater than the node element (A)</p> Signup and view all the answers

What is the defining characteristic of a binary sorted tree?

<p>Left subtree contains elements less than or equals to the node element, and right subtree contains elements greater than the node element (A)</p> Signup and view all the answers

What action should be taken if the target element in a binary search tree is greater than the node element?

<p>Go down the right subtree (D)</p> Signup and view all the answers

What is the next step if the target element in a binary search tree is less than or equal to the node element?

<p>Go down the left subtree (C)</p> Signup and view all the answers

What is the iterative process for finding a target element in a binary search tree?

<p>Compare, go left or right, repeat until found (B)</p> Signup and view all the answers

What does the constructor of BSTreeNode take as parameters?

<p>Element value, left child, and right child (D)</p> Signup and view all the answers

Which methods would you expect to find in the BSTreeNode class for accessing the left and right children?

<p>getLeft() and getRight() (A)</p> Signup and view all the answers

What type of data does the element variable in the BSTreeNode class store?

<p>Generic type (E) (C)</p> Signup and view all the answers

How would you initialize a new leaf node with the element value '42'?

<p>new BSTreeNode(42, null, null) (B)</p> Signup and view all the answers

What happens when a node in a B-tree becomes full?

<p>It needs to split into 2 nodes (D)</p> Signup and view all the answers

Which method would you use to insert a new element into a binary search tree through a BSTreeNode instance?

<p>insertElement(E elem) (C)</p> Signup and view all the answers

If you want to traverse the elements of a binary search tree in an in-order fashion, which method would you typically use in the BSTreeNode class?

<p>inOrderTraversal() (C)</p> Signup and view all the answers

How would you check if a specific element exists in a binary search tree represented by a BSTreeNode instance?

<p>containsElement(E elem) (C)</p> Signup and view all the answers

What method might you use to remove a specific element from a binary search tree through a BSTreeNode instance?

<p>removeElement(E elem) (D)</p> Signup and view all the answers

What is the purpose of the parameterless constructor public BSTree() in the BSTree class?

<p>It initializes an empty BST. (C)</p> Signup and view all the answers

How is the root of the binary search tree initialized in the parameterized constructor public BSTree(E element)?

<p>this.root = new BSTreeNode(element, null, null); (C)</p> Signup and view all the answers

How would you check if a BSTree instance is empty?

<p>isEmpty() (D)</p> Signup and view all the answers

How would you create an empty binary search tree using the BSTree class?

<p>BSTree emptyTree = new BSTree(); (D)</p> Signup and view all the answers

Flashcards are hidden until you start studying

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser