What is the performance for binary search on a doublylinked

What is the performance for binary search on a doubly-linked list? Justify your answer.

Solution

In binary search tree, each node contains two pointers, one for left child and other for right child. Similarly, in a doubly linked, each node contains two pointers, one for next node and other for previous node.

Converting binary tree to doubly linked list , we first traverse binary tree in inorder manner and at each node, link left pointer of current node to inorder predecessor. Since it is decided that left pointer will point to previous node, previous node of current node will be the node which was visited just before current node in traversal. Hence, link left pointer of current node to inorder predecessor.

Inorder traversal gives opportunity to change current node’s left pointer to point to previous node as in inorder traversal we will never need to traversal left subtree of current node again.