Binary Search Tree and Doubly Linked List

1. Problem Description

Given a binary search tree, convert it into a sorted doubly linked list. No new nodes may be created; only the pointers between existing tree nodes may be adjusted.

2. Approach

• Inorder traversal
• Recursion Unlike Flatten Binary Tree to Linked List, this problem uses inorder traversal and produces a sorted doubly linked list, while that problem uses preorder traversal.

3. Implementation

3.1. Inorder Traversal

package main

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 *
 * @param pRootOfTree TreeNode class
 * @return TreeNode class
 */
// Time: O(N)
// Space: O(N)
func Convert(pRootOfTree *TreeNode) *TreeNode {
	if pRootOfTree == nil {
		return nil
	}

	nodes := make([]*TreeNode, 0)
	midOrdered(pRootOfTree, &nodes)

	for i := 0; i < len(nodes)-1; i++ {
		nodes[i].Right = nodes[i+1]
		nodes[i+1].Left = nodes[i]
	}
	nodes[0].Left = nil
	nodes[len(nodes)-1].Right = nil

	return nodes[0]
}

func midOrdered(node *TreeNode, nodes *[]*TreeNode) {
	if node == nil {
		return
	}

	midOrdered(node.Left, nodes)
	*nodes = append(*nodes, node)
	midOrdered(node.Right, nodes)
}

3.2. Recursion

func Convert2(pRootOfTree *TreeNode) *TreeNode {
	if pRootOfTree == nil {
		return nil
	}

	leftNode := Convert2(pRootOfTree.Left)
	rightNode := Convert2(pRootOfTree.Right)

	// The left subtree needs one more conversion step: find its rightmost node
	// The right subtree does not, because the node needed is already its leftmost node
	retNode := leftNode
	if leftNode != nil {
		leftNode = findRight(leftNode)
	} else {
		retNode = pRootOfTree
	}

	// Connect the parent to the left and right subtrees
	pRootOfTree.Left = leftNode
	pRootOfTree.Right = rightNode

	// Connect the left and right subtrees back to the parent
	if leftNode != nil {
		leftNode.Right = pRootOfTree
	}
	if rightNode != nil {
		rightNode.Left = pRootOfTree
	}
	return retNode

}

func findRight(node *TreeNode) *TreeNode {
	for node.Right != nil {
		node = node.Right
	}
	return node
}

4. References

• Binary Search Tree and Doubly Linked List - NowCoder