• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Linked List V/S Binary Search Tree

March 19, 2014 by Dhaval Dave

Linked List :

Node(1) -> Node(2) -> Node(3) -> Node(4) -> Node(5) -> Node(6) -> Node(7)
  • In linked list, the items are linked together through a single next pointer.
  • Next Node’s Key Can be larger or samller then previous Node.
  • Not Sorted
  • Time Complexity of Search :O(n) Insert : O(1) Delete : O(1) {if you have use optimized method }


Binary Search Tree:

           [4]
          /   \
       [2]     [6]
      /  \    /   \
    [1]  [3] [5]   [7]
  • In a binary tree, each node can have 0, 1 or 2 sub nodes.
  • The key of the left node is lesser than the key of the node and the key of the right node is more than the node
  • Sorted
  • Time Complexity of Search : O(log(n)) Insert : O(log(n)) Delete : O(log(n))
References:
http://bigocheatsheet.com/

Similar Articles

Filed Under: problem Tagged With: Binary Search Tree, BST, Linked List

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Printing intermediate Integers between one element & next element of array

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

Find if a binary tree is height balanced ?

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Find min element in Sorted Rotated Array (Without Duplicates)

Reversal of LinkedList

Knight Tour Problem (Graph – Breadth First Search)

Python Array String

Length of the longest substring without repeating characters

Microsoft BING Interview Experience

1014 Practice Question of New GRE – Princeton

Find Percentage of Words matching in Two Strings

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

strtok()

Stickler thief

Generic Object Oriented Stack with Template

Get Minimum element in O(1) from input numbers or Stack

Fibonacci Hashing & Fastest Hashtable

Possible sizes of bus to carry n groups of friends

Edit Distance ( Dynamic Programming )

Urban Ladder Written Test.

Given a string, find the first character which is non-repetitive

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Generate next palindrome number

Test Cases for Round Function

Reverse a Linked List in groups of given size

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Coin Collection Dynamic Programming

Find the element that appears once others appears thrice

C++ OOPs Part2

Copyright © 2025 · Genesis Framework · WordPress · Log in