BST(Binary Search Tree)

Data Structure Review

• ArrayList: The ArrayList has a time complexity of O(1) when adding or removing elements at the end, but it has a time complexity of O(n) when adding or removing elements at the beginning.
• Singly-Linked List w/ Tail:In a singly-linked list with a tail reference point, adding elements (at the front or back) and deleting elements from the front all have a time complexity of O(1). However, deleting elements from the back has a time complexity of O(n).
• Doublely-Linked List w/ Tail: In a doubly-linked list with a tail reference point, both adding and deleting elements have an outstanding time complexity of O(1).

However, all of the above data structures have an average time complexity of O(n) for searching and accessing elements. (With the exception of ArrayList, which has a time complexity of O(1) for accessing elements through indexing.) In the case of a Stack, if you want to find a specific element, you would need to pop all the elements of the stack and compare each of them with the target data. A similar procedure is required in Deque or Queue as well.

Trees?

• A trees are linked structures that are connected and do not have cycles.
• Can be implemented in multiple ways depending on the details of the type of tree.
• Trees can be further categorized if we give them some other properties: Shape: What is the structure of the node in the tree? Order: How is the data arranged in the tree?
• Searching and accessing can be achieved in O(1) time complexity.

Binary Trees

Binary Trees are defined by three properties.

1. Every node can have at most two children.
2. Child nodes are labeled left and right child.
3. Left child always precedes the right in the order of the nodes, not the data.

Binary Trees have three shape properties.

1. Full Tree: Each node must have 0 or 2 children.
2. Complete Tree: Every level must be filled except for the last one, which is filled left to right.
3. Degenerate Tree: All nodes have 1 child.

Binary Search Tree

Binary Search Trees are a type of Binary tree that inherit all the properties from Binary Trees and enforce a data order property where left child data is less than parent data which is less than the right child data.

Depth (Recursive) Traversals

In a Binary Search Tree (BST), there are three main traversal strategies for accessing data.

• Pre-order Recursive traversal: C-L-R
• Post-order Recursive traversal:L-R-C
• In-order Recursive traversal: L-C-R

Breadth (Iterative) Traversals

The Breadth traversal strategy is straightforward. It accesses data by traversing each level of the tree. A virtual Queue is created, and the traversal starts by accessing the root node, which represents the topmost level. Then, while moving to the next level, the traversal iterates from left to right, continuously enqueueing nodes into the Queue.