loading...

Binary Search Trees

jjb profile image JB Updated on ・3 min read

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Note: I will be referring to Binary Search Trees as BST for the duration of this post.

Resources

  1. Tree & Binary Tree Overviews
  2. BST Overview
  3. More In Depth BST Overview
  4. Search and Insert
  5. Deletes
  6. Breadth First Search
  7. Depth First Search Overview
  8. Depth First Search Implementation

Takeaways:

  • The top level node is called the root node.
  • Nodes to the left are smaller than their parent nodes. Nodes to the right are larger than their parents.
  • A node at the bottom of a tree, meaning it has no child nodes (i.e no reference to a node left or right), is called a leaf node.
  • There are two main ways of traversing a BST: Depth First Search (DFS) and Breadth First Search (BFS).
  • There are three main ways you can perform a DFS: Preorder, Inorder, and Postorder.
  • BFS traverses the tree level by level (so width ways or across the tree). DFS traverses the tree by going down it, and it starts with the left side of the tree.
  • The left side of a root node is called the left subtree and the right is the right subtree. This is not exclusive to a root node, any node can have a subtree off of it.
  • Space for a BST is O(n).
  • Time complexity of operations is good - not the fastest, but not the slowest. All operations on a balanced BST are O(log n) (Logarithmic). For an unbalanced BST all operations are O(n).
  • Due to the time complexity being worse for an unbalanced tree, it is a good idea to periodically rebalance a BST (which I plan to learn more about - maybe starting here).
  • An unbalanced BST is one where there are more levels than necessary, making operations perform less than optimal. For example the height of a BST might be five levels, but the same BST could be represented in three levels instead by reorganizing the nodes. This regorganization is called rebalancing.

Overall the hardest part about implementing a BST is the delete operation. Probably the hardest part was dealing with deleting a node with two child nodes. I learned that in this instance you need to find the inorder successor* and essentially move it to where the deleted node was.

*An inorder successor of a node is the next node in the inorder traversal of the BST. I.E. If you looked at an inorder sequence of nodes, it would be the one after the node being deleted.

As the delete operation was challenging, I added comments explaining it step by step. There are more succinct ways to do it than I chose - but I feel my implementation is easier to follow than most.

Here's the finished implementation of a BST with some test code:

As always, if you found any errors in this post please let me know!

CS Level Up Series (30 Part Series)

1) CS Level Up Series Introduction 2) Dynamic Arrays 3 ... 28 3) Linked Lists 4) Stacks 5) Queues 6) Hash Tables 7) Binary Search Trees 8) Binary Heaps 9) Priority Queues 10) Graphs 11) Tries 12) Binary & Bit Manipulation 13) Common Sorting Algorithms 14) Searching Algorithms 15) Permutations, Combinations, & Subsets 16) NP-Complete & Fibonacci Heap 17) Detecting Graph Cycles With Depth-First Search 18) Finding Shortest Paths In Graphs (using Dijkstra's & BFS) 19) Topological Sorting of Directed Acyclic Graphs (DAGs) 20) Finding Articulation Points & Bridges in Undirected Graphs 21) Finding Strongly Connected Components in Directed Graphs using Tarjan's Algorithm 22) Checking If An Undirected Graph Is Bipartite 23) Extending An Iterator 24) Union-find (Disjoint-set) 25) Minimum Spanning Tree (Kruskal's Algorithm) 26) Sliding Window Technique 27) String Searching Using Rabin-Karp 28) Fenwick Tree (Binary Indexed Tree) 29) Dynamic Programming 30) Traveling Salesman Problem

Posted on Nov 17 '19 by:

Discussion

markdown guide