`

Convert a BST to a sorted circular doubly-linked list

 
阅读更多

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.


If the problem statement is still not clear to you, below is a pictorial representation of what you need to do:

 

i) an ordered binary tree (BST) storing numbers from 1 – 5.
ii) original tree converted to a sorted circular doubly-linked list. Its left and right pointers were modified to point to its previous and next node.

I originally read this interesting problem here: The Great Tree-List Recursion Problem.

Hint:
Think of in-order traversal. How do you ensure that the last element’s right pointer points back to the first element?

A circular doubly-linked list. Think of the left and right pointers in a tree as synonymous to the previous and next pointers in a list.

Solution: 
When I first see this problem, my first thought was in-order traversal. Couldn’t we modify the nodes’ left and right pointers as we do an in-order traversal of the tree? However, we have to beware not to modify the pointers and accessing it at a later time.

As we traverse the tree in-order, we could safely modify a node’s left pointer to point to the previously traversed node as we never use it once we reach a node. We would also need to modify the previously traversed node’s right pointer to point to the current node. Note: The previously traversed node meant here is not its parent node. It is the node’s previous smaller element.

Easy approach, right? But wait, we are still missing two more steps. First, we did not assign the list’s head pointer. Second, the last element’s right pointer does not point to the first element (similar to the first element’s left pointer).

How do we solve this? My approach is pretty easy: Just update the current node’s right pointer to point back to the head and the head’s left pointer to point to current node in each recursive call. As the recursion ends, the list’s head and tail would be automagically updated with the correct pointers. Don’t forget to check for this special case: A list with only one element should have its left and right pointers both pointing back to itself.

A double-linked list with a length of one.

Do you think this approach works? I bet it did! The run time complexity for this solution is O(N) since we are essentially doing a modified in-order traversal. It does have some extra assignments in each recursive call though. But overall I am quite satisfied with this approach because it is intuitive and easy to follow. Besides, we are adapting an existing algorithm (in-order traversal) to solve this problem, isn’t this just neat?

private TreeNode prev;
private TreeNode head;
public TreeNode bstToSortedDLL(TreeNode node) {
	if(node == null) return null;
	bstToSortedDLL(node.left);
	node.left = prev;
	if(prev != null) {
		prev.right = node;
	} else {
		head = node;
	}
	prev = node;
	TreeNode right = node.right;
	head.left = node;
	node.right = head;
	bstToSortedDLL(right);
	return head;
}

 

Reference:

http://articles.leetcode.com/2010/11/convert-binary-search-tree-bst-to.html

分享到:
评论

相关推荐

    AVL和红黑树性能对比

    AVL和红黑树性能对比,有详细的测试数据。AVL和红黑树都是平衡树。...a in-order doubly linked list is advantageous when traversal is very common; and right-threaded nodes perform poorly.

    程序员面试题精选100题(自己整理)

    2. **排序的双向链表(Sorted Doubly Linked List)** 排序的双向链表是一种链表,其中每个节点包含数据和两个指针,一个指向前一个节点,另一个指向后一个节点。链表中的元素按升序或降序排列。双向链表允许从任一...

    程序员面试题精选(附答案及分析)

    本题是关于将二元查找树(Binary Search Tree, BST)转换为排序的双向链表(Sorted Doubly Linked List)的问题。这是一道经典的面试题,因为它涉及到数据结构的转换,递归思想的应用,以及链表操作。 二元查找树是...

    程序员编程100例.doc

    编程100例中的第(01)题是关于将二元查找树(Binary Search Tree, BST)转换成一个排序的双向链表(Sorted Doubly Linked List)。这是一个经典的计算机科学问题,主要涉及数据结构的转换。在解决这个问题时,我们...

    数据结构算法设计笔试面试题5.docx

    这是一道关于数据结构转换的面试题,要求将一棵二元查找树(Binary Search Tree, BST)转换成一个排序的双向链表(Sorted Doubly Linked List),保持原有的顺序。二元查找树的特点是左子树上所有节点的值均小于它的...

    70道常见面试算法笔试题

    本问题聚焦于一道具体的算法题——将二元查找树(Binary Search Tree, BST)转化为排序的双向链表(Sorted Doubly Linked List)。下面我们将详细解析这个问题及其解决方案。 二元查找树是一种特殊的二叉树,其中每...

Global site tag (gtag.js) - Google Analytics