CSC 1061: Binary Search Tree

Course: CSC 1061

Binary Search Tree (BST)

• A BST is a non-linear data structure.
• Unlike linear structures (arrays, linked lists, etc.), BSTs provide faster data access.
• BSTs organize data hierarchically, with a root node at the top.
• The relationship between nodes is parent/child. Each node has at most one parent and two children (left and right).

BST Terms

• Root: The topmost node in the tree.
• Edge: The link (pointer) connecting two nodes.
• Leaf: A node with no children.
• Depth of a Node: The number of edges from the root to the node.
• Height of a Tree: The height of the root node or the depth of the deepest node.
• Degree of a Node: The number of branches of that node.
• Forest: A collection of disjoint trees.

BST Overview (Computer Science Perspective)

• The root is at the top.
• The relationship between a node and the node below it is parent/child relationship.
• A node can only have one parent.
• A tree is often used to represent a hierarchy.
• A directory structure on a UNIX machine has a tree structure.
• The root directory is the top.
• The BST is useful for quickly storing and retrieving sorted data.

BST (Programiz)

• A binary tree where each node contains data and pointers to at most two children (left and right).
• In a BST, the left pointer is used to store nodes with values less than or equal to the parent node.
• The right pointer stores children with values greater than the parent node.
• A node with no children is called a leaf node.

Binary Tree Data Structure Class

• A container of BinNode elements stored in the heap at runtime.
• A BinNode pointer is allocated with each addition to the tree.
• Memory is deallocated when a node is removed, ensuring the tree only uses the necessary memory.

BinNode (Element Class)

• A helper class for BST.
• Stores fundamental data and pointers of the current tree element (left and right children).
• The structure of the element stored in the BST.
• Encapsulates the data, left pointer (referencing left child), and right pointer (referencing right child).
• Not dynamic: It does not allocate or deallocate memory.
• Not a container: It cannot add, remove, or find elements within the tree.

BST: Creating the Tree

• Initialize root to nullptr to signify an empty tree in the constructor.

BST: IsEmpty

• Check if a tree is empty by comparing the root pointer to nullptr.
• The root pointer can either have an address (empty) or is nullptr(not empty).

BST: Adding to an Empty Tree

• Allocate a new BinNode for the item..
• Set the root to the new node.

BST: Adding to a Non-Empty Tree

• Traverse the tree to find the correct position for addition based on the comparison to the parent node.
• Create a loop to add recursively to the subtree.

BST Traversals

• Traversing a tree involves visiting every node.

• Linear structures (e.g. arrays, linked lists) traverse in a single path.

• Hierarchical structures (e.g., trees) can be traversed in multiple ways using recursive calls to enable traversal back through subtrees.

• Inorder: Left, Process, Right

• Preorder: Process, Left, Right

• Postorder: Left, Right, Process

• Backward Inorder: Right, Process, Left

BST Traversal: Design

• A function to handle recursive calls for traversal, handling the potential nullptr cases.

BST Traversal: In-Order

• Recursive function that performs an in-order traversal of a BST.
• Prints the values in the tree in an ascending order.

BST Rule of 3

• Copy Constructor: Makes a deep copy of the source tree on the heap.
• Assignment Operator: Makes a deep copy of the source tree on the heap.
• Destructor: Destroys all memory allocated for the tree on the heap.

BST: Deep Copy of Memory

• Check for self-assignment.
• Free existing memory
• Initialize memory of the new tree as nullptr.
• Traverse source tree using a recursive helper function to perform a deep copy of each node.
• Copy each item in the source tree into the destination tree based on the traversal order and the comparison of data values.