Implementation of Binary Search Tree using linked list in javascript-CodePudding

I want to ask that is implementing a BST and implementing it with linked list are the same ? For example, to implement a binary search tree, we have to create a node with information of its left and right child, similar is the situation when we use the linked list as a node consists of three parts such as data, left and right child. Then what is the difference ? Thank you minds in advance.

I implemented the BST and applied inorder traversal and searched the elements. But I find it difficult to imbibe the relation between binary search tree and the linked list. Correct me please.

CodePudding user response：

The meaning of the links is different in binary search trees and doubly-linked lists.

In a doubly-linked list, the left link of one node is the inverted right link of another node (and vice versa):

1 <-> 2 <-> 3 <-> 4

In other words, we always have

left(right(node)) = node

if node has a right link and

right(left(node)) = node

if node has a left link.

But the search tree

the node 4 is connected to three links: one incoming and two outgoing, and we have

left(right(2)) = left(4) = 3

CodePudding user response：

Double Linked List

Linked List is linear data structure. As geeksforgeeks.org says:

Data structure where data elements are arranged sequentially or linearly where each and every element is attached to its previous and next adjacent is called a linear data structure. In linear data structure, single level is involved. Therefore, we can traverse all the elements in single run only. Linear data structures are easy to implement because computer memory is arranged in a linear way. Its examples are array, stack, queue, linked list, etc.

Item_1 <--> Item_2 <--> Item_3 <--> Item_4 <--> Item_5 <--> Item_6 <--> Item_7

Binary search tree

Binary search tree is non-linear data structure. As geeksforgeeks.org says:

Data structures where data elements are not arranged sequentially or linearly are called non-linear data structures. In a non-linear data structure, single level is not involved. Therefore, we can’t traverse all the elements in single run only. Non-linear data structures are not easy to implement in comparison to linear data structure. It utilizes computer memory efficiently in comparison to a linear data structure

                 8
                / \
               3   10
              / \    \
             1   6    14
                / \     \
               4   7     15