Big O Complexity in Binary Search Tree(BST)

In the absolute worst case, a binary tree with N elements would be like a linked list.
Hence, there would be N levels, and a search would take N traversals.

                                    ~ Root ~
                                      ____
                                     | 42 |
                                     |____|
                                    /      \
                               ____/        \
                              | 13 |         X
                              |____|
                             /      \
                        ____/        \
                       | 11 |         X
                       |____|
                      /      \
                     /        \
                  ...          X

That’s why it’s O(N) in the worst case.
And this is why we need to balance the trees to achieve O(log N) search.

Related Posts:

  1. Why lookup in a Binary Search Tree is O(log(n))?
  2. Difference between binary tree and binary search tree
  3. How can I implement a tree in Python?
  4. JavaScript hashmap equivalent
  5. Is there an easy way to make a min heap in C++?
  6. Explanation of runtimes of BFS and DFS
  7. Array versus linked-list
  8. A proper way to create a matrix in c++
  9. Does Java support structs?
  10. Why does the C++ STL not provide any “tree” containers?
  11. Does Java support structs?
  12. What do I use for a max-heap implementation in Python?
  13. Minimum Spanning Tree: What exactly is the Cut Property?
  14. Quick Way to Implement Dictionary in C
  15. How does a hash table work?
  16. How to implement a binary search tree in Python?
  17. What is the difference between a map and a dictionary?
  18. How do I instantiate a Queue object in java?
  19. Linked List vs Vector
  20. Implementing a HashMap in C
  21. Why is O(n) better than O( nlog(n) )?
  22. Chained Hash Tables vs. Open-Addressed Hash Tables
  23. Library for the Basic Data Structures, such as Queue, in C
  24. Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
  25. Queue vs Dequeue in java
  26. What is the difference between Python’s list methods append and extend?
  27. Search for words with telephone numbers from 2-3-4 tree
  28. What does O(log n) mean exactly?
  29. what does O(N) mean [duplicate]
  30. What does O(log n) mean exactly?
  31. How to implement a tree data-structure in Java?
  32. What is the difference between tree depth and height?
  33. Bad Operand Types for Binary Operator “>”?
  34. How can I remove a key from a Python dictionary?
  35. Extract rows from R data frame based on factors (strings)
  36. What is copy-on-write?
  37. Priority queue in .Net
  38. Understanding Time complexity calculation for Dijkstra Algorithm
  39. Time complexity of a Priority Queue in C++
  40. A proper way to create a matrix in c++
  41. How can I remove a key from a Python dictionary?
  42. golang why don’t we have a set datastructure [closed]
  43. Java implementation for Min-Max Heap?
  44. What are the differences between B trees and B+ trees?
  45. Determining complexity for recursive functions (Big O notation)
  46. Why is Dictionary preferred over Hashtable in C#?
  47. Example of O(n!)?
  48. Python Sets vs Lists
  49. Big O, how do you calculate/approximate it?
  50. Does VBA have Dictionary Structure?
  51. In Python, when to use a Dictionary, List or Set?
  52. HashMap get/put complexity
  53. O(n log n) vs O(n) — practical differences in time complexity
  54. Tree data structure in C#
  55. Trie complexity and searching
  56. Is log(n!) = Θ(n·log(n))?
  57. Difference between a HashMap and a dictionary ADT
  58. How to calculate big-theta
  59. What is the time complexity of while loops?
  60. struct has no member named
  61. creating an array of structs in c++
  62. member access within null pointer of type ‘struct ListNode’
  63. What is the difference between an Abstract Data Type(ADT) and a Data Structure?
  64. Hash table runtime complexity (insert, search and delete)
  65. Which is better: O(n log n) or O(n^2)
  66. Order functions by growth rate
  67. Get keys from HashMap in Java
  68. Big Oh for (n log n)
  69. Difference between Big-O and Little-O Notation
  70. What is the big-O of the function (log n)^k
  71. How do I find the time complexity (Big O) of while loop?
  72. creating an array of structs in c++
  73. What does the MATLAB error “scalar structure required for this assignment” refer to in this statement?
  74. How to return nothing from a function that returns value?
  75. Computational complexity of Fibonacci Sequence
  76. Which algorithm is faster O(N) or O(2N)?
  77. What do I use for a max-heap implementation in Python?
  78. A tool for calculating the big-O time complexity of Java code? [closed]
  79. How to print binary tree diagram in Java?
  80. Difference between Big-Theta and Big O notation in simple language
  81. Time complexity of nested for-loop
  82. How are the following functions O(N^3)?
  83. When should I use a List vs a LinkedList
  84. Are there any real O(n^n) algorithms?
  85. What is O(log(n!)) and O(n!) and Stirling Approximation
  86. What’s the difference between the data structure Tree and Graph?
  87. invalid use of template name without an argument list
  88. Array of Linked Lists C++
  89. Running time of algorithm A is at least O(n²) – Why is it meaningless?
  90. “Cannot allocate an object of abstract type” error

Leave a Comment