Binary Trees Overview

Binary Trees

• A binary tree is a tree where each node can have a maximum of two children.
• The height of an empty binary tree is -1.
• The degree of a node is the number of its children.
• Binary trees are not used for storing relational data.
• Huffman coding uses a binary tree.
• Decision trees are used for machine learning.
• Finding the height of a general tree can be done through iterative or recursive traversal.
• Counting the nodes in a general tree can be done using any traversal method.
• "Left, Root, Right" traversal order is called inorder.
• Deleting a node involves replacing it with its inorder successor or predecessor.
• Postorder traversal prints the leaves first.
• Binary tree node components include data and left/right child pointers.
• Inserting an element into a binary tree has a time complexity of O(n).
• In a binary search tree (BST), the left subtree contains nodes with smaller keys than the root and the right subtree contains nodes with larger keys than the root.
• Database indexing is a real-world BST application.
• Searching in a balanced BST has a time complexity of O(log n).
• Inorder traversal produces a sorted sequence of elements in a BST.

Heaps

• Heaps are unordered.
• BSTs are ordered.
• Heaps are complete binary trees.
• Heaps always have a complete structure, unlike BSTs which can be unbalanced.
• Percolate up is used to restore the heap property after an insertion.
• Extracting the maximum element from a MaxHeap has a time complexity of O(log n).
• In MinHeaps, the root has the smallest value, and all leaf nodes have larger values.
• The parent of a node (i) in a heap array is calculated as (i - 1) / 2.
• Sorting an array can use heap properties for optimization.
• A heap can be represented as a complete binary tree.
• The minimum number of nodes in a heap of height h is 2^(h-1) .
• Heaps provide predictable structure and easy insertion/deletion compared to BSTs.
• Heapify builds a heap from an array.
• Removing the largest element from a MaxHeap involves removing the root and reheapifying.
• Inserting a new element is more efficient in a heap compared to an array.
• The heap property ensures the smallest element is at the root of a MinHeap.
• A heap in an array uses compact storage without pointers.
• Building a heap from an unsorted array has a time complexity of O(n).

This quiz covers the fundamental concepts of binary trees, including their structure, traversal methods, and applications in areas like Huffman coding and machine learning. Test your understanding of key definitions and operations related to binary trees.