CareerCup

Method1: Put inorder traversal in an array. Traverse the array changing right pointers and setting left pointers to null.

Method2: Start from root. Until current root has left children, rotate right about the root. (After rotating right, current root is the left child of previous root). If current root has no left child, traverse in the right subtree until you find a node which has a left child. Repeat the rotation. Once you reach a leaf when traversing down right subtree, stop.

O(n) complexity and O(log n) memory assuming the tree's balanced:

static class Node{
    int value;
    Node left, right;
}

public static Node flattenTree(Node root){
    if(root == null){
        throw new NullPointerException();
    }
    
    Node[] flatten = flatten(root);
    return node[0];
}

private static Node[] flatten(Node node){
    if(node.left != null){
        Node[] leftResult = flatten(node.left);
        node.left = null;
        if(node.right != null){
            Node[] rightResult = flatten(node.right);
            leftResult[1].right = node;
            node.right = rightResult[0];
            leftResult[1] = rightResult[1];
            return leftResult;
        }
        else{
           leftResult[1].right = node;
           leftResult[1] = node;
           return leftResult;
        }
    }
    else if(node.right != null){
        Node[] rightResult = flatten(node.right);
        node.right = rightResult[0];
        rightResult[0] = node;
        return rightResult;
    }
    return new Node[]{node, node};
}

you can Traverse the BST in In-Order this will give the element in descending order.

class Node {
public:
  int val;
  Node *left, *right;
  Node(int v) :val(v), left(nullptr), right(nullptr) {};
};

Node* flat(Node *root) {
  if (!root) return root;
  Node *start = root, *p = root, *tmp = nullptr;
  while (start->left) start = start->left;
  while (p) {
    if (!p->left) { p = p->right; continue; }
    tmp = p->left;
    while (tmp->right) tmp = tmp->right;
    tmp->right = p;
    p->left = nullptr;
    p = tmp;
  }
  return start;
}

class Node {
public:
  int val;
  Node *left, *right;
  Node(int v) :val(v), left(nullptr), right(nullptr) {};
};

Node* flat(Node *root) {
  if (!root) return root;
  Node *start = root, *p = root, *tmp = nullptr;
  while (start->left) start = start->left;
  while (p) {
    if (!p->left) { p = p->right; continue; }
    tmp = p->left;
    while (tmp->right) tmp = tmp->right;
    tmp->right = p;
    p->left = nullptr;
    p = tmp;
  }
  return start;
}

public void flatten(TreeNode root) {	        
		  helper (root);
	  }
	  
	    private TreeNode helper (TreeNode root){
		  if (root == null) {
			  return null ;
		  }
		  if (root.left == null && root.right == null) {
			  return root ;
		  }
		  TreeNode left = helper (root.left);
		  TreeNode right = helper (root.right);
		  root.right = left ;
		  TreeNode p = root ;
		  while (p != null && p.right != null) {
			  p = p.right ;
		  }
		  if (p != null) {
			  p.right = right ;
		  }
		  root.left = null ;
		  return root ;

}

public void flatten(TreeNode root){
	if(root == null){
		return;
	}
	Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
	while(root != null && !stack.isEmpty){
		if(root.left != null){
			if(root.right != null){
				stack.push(root.right);
			}
			root.right = root.left;
			root.left == null;

		} else{
            if(!stack.isEmpty()){
            	TreeNode temp = stack.pop;
            	root.right = temp;
            }
		}
		root = root.right;
	}

}

//Used an inorder traversal to visit the nodes in the tree. When visited, a node's left child is removed and the node is added to a stack
//O(n) time O(1) Space

public class Node 
{
	int value;
	Node left;
	Node right;
	
	public Node(int v)
	{
		value=v;
	}
}

public class BSTService
{
	public static Node flattenTree(Node n) throws NullPointerException
	{
		if(n==null)
		{
			throw new NullPointerException("input tree cannot be null");
		}
		Stack s=new Stack();
			flatten(s,n);
	}
	private void flatten(Stack s,Node r)
	{
		if(r==null)
		{
			return void;
		}
		flatten(s,r.left);
		if(s.isEmpty())
		{
			r.left=null;
			s.push(r);
		}else
		{
			r.left=null;
			s.peek.right=r;
			s.push(r);
		}
		flatten(s,r.right);
	}
	
	public static void main(String[] args)
	{
		Node n=new Node(24);
		Node l1=new Node(18);
		n.left=l1;
		l1.left=new Node(16);
		l1=l1.left;
		l1.right=new Node(17);
		Node r1=new Node(30);
		n.right=r1;
		r1.left=(26);
		r1.right=(34);
		r1=r1.right;
		r1.right=new Node(35);
		
		Node n=BSTService.flattenTree(n);
	}
}

The first solution is a somewhat naive recursive attempt. Because flattenTree returns the root of the flattened tree, and we need to add the current node as a child of the only leaf node in the flattened tree, we have to traverse the left result each time.

That makes this worst case O(n^2).

Node flattenTree(Node n) {
	if (n == null)
		return n;
	
	if (n.Left == null && n.Right == null)
		return n;

	var leftResult = flattenTree(n.Left);

	var m = leftResult;
	if (m != null) {
		while (m.Right != null) {
			m = m.Right;
		}
		m.Right = n;
		n.Left = null;
		n = leftResult;
	}

	n.Right = flattenTree(n.Right);
}

The second solution attempts to get rid of the extra unnecessary traversals by returning both the root and leaf node in the result of a helper method which recurses. This one is O(n).

private class Flattener {
	
	public static Node flattenTree(Node n) {
		var result = flatten(n);
		if (result == null)
			return null;
		return result.First;
	}

	private class FlatResult {
		Node Root;
		Node Leaf;
	}

	private static FlatResult flatten(Node n) {
		if (n == null)
			return null;

		if (n.Left == null && n.Right == null){
			return new FlatResult { Root = n, Leaf = n };
		}

		var leftResult = flatten(n.Left);

		if (leftResult != null) {
			leftResult.Leaf.Left = n;
			n = leftResult.Root;
		}

		var leaf = null;
		var rightResult = flatten(n.Right);
		if (rightResult != null) {
			n.Right = rightResult.Root;
			leaf = rightResult.Leaf;
		}

		return new FlatResult { Root = n, Leaf = leaf }
	}
}

public class TreeNode
{
	public TreeNode() : this(0) { }

	public TreeNode(int value)
	{
		Value = value;
		Left = null;
		Right = null;
	}

	public int Value;
	public TreeNode Right;
	public TreeNode Left;
}


public TreeNode FlattenTree(TreeNode root)
{
	if (root == null)
		return null;

	TreeNode header = new TreeNode();
	TreeNode p = header;
	Stack<TreeNode> stack = new Stack<TreeNode>();
	stack.Push(root);

	while (stack.Count > 0)
	{
		TreeNode node = stack.Pop();
		if (node.Left == null && node.Right == null)
		{
			p.Right = node;
			p = node;
		}
		else
		{
			if (node.Right != null)
				stack.Push(node.Right);

			stack.Push(node);

			if (node.Left != null)
				stack.Push(node.Left);

			node.Left = node.Right = null;
		}
	}

	return header.Right;
}

1 Find the left most node (this will be the root of the flattened tree)
2. rotate right
3. flattern right sub tree
4. return to parent node and repeat from step 2
Optimization : Keep a pointer to the leafNode of the flatterned subtree

Here is the C# implementation

public static TreeNode Flattern(TreeNode bst)
{
	//The Flatterned Tree
	TreeNode flattenedBST = null;
	//The leaf node of the flatterned tree. For Optimization
	TreeNode flatternedLeafNode = null;

	return Flattern(bst, ref flattenedBST, ref flatternedLeafNode);
}

private static TreeNode Flattern(TreeNode bst, ref TreeNode flattenedBST, ref TreeNode flatternedLeafNode)
{
	if (bst == null)
	{
		return bst;
	}

	if (bst.left != null)
	{
		flattenedBST = Flattern(bst.left, ref flattenedBST, ref flatternedLeafNode);
		flatternedLeafNode.right = bst;
	}
	else if (bst.left == null) 
	{
		if (flattenedBST == null)
		//This is the smallest in the whole tree, which is the root of the flattened tree
		{
			flattenedBST = bst; 
		}
		else 
		//this is the next smallest node
		{
			flatternedLeafNode.right = bst;
		}
	}
	//Set the last element in the partially flattned tree
	flatternedLeafNode = bst;

	//We have processed the left sub tree now
	bst.left = null; 
	Flattern(bst.right, ref flattenedBST, ref flatternedLeafNode);

	return flattenedBST;
}

Slightly modified in-order traversal can do it in O(n) complexity and O(1) space

class BSTFlattenRight
{
	public static void main(String[] st)
	{
		BTNode n1=new BTNode(1);
		BTNode n2=new BTNode(2);
		BTNode n3=new BTNode(3);
		BTNode n4=new BTNode(4);
		BTNode n6=new BTNode(6);
		BTNode n7=new BTNode(7);
		BTNode n10=new BTNode(10);
		BTNode n11=new BTNode(11);
		BTNode n14=new BTNode(14);
		BTNode n15=new BTNode(15);
		
		n1.right=n2;
		n3.left=n1;
		n3.right=n6;
		n6.left=n4;
		n6.right=n7;
		n10.left=n3;
		n10.right=n14;
		n14.left=n11;
		n14.right=n15;
		
		System.out.println("tree before:");
		in_order(n10);
		System.out.println();
		
		BSTFlattenRight obj=new BSTFlattenRight();
		BTNode root=obj.flat(n10);
		print(root,"after transformation");
	}
	
	static void in_order(BTNode node)
	{
		if(node.left!=null)
			in_order(node.left);
		System.out.print(node.data+", ");
		if(node.right!=null)
			in_order(node.right);
	}
	static void print(BTNode node,String msg)
	{
		System.out.println(msg);
		while(node!=null){
			System.out.print(node.data+", ");
			node=node.right;
		}
		System.out.println();
	}
	BTNode presentRightMost=null;
	BTNode flat(BTNode node)
	{
		BTNode parent;
		if(node.left==null)
			parent=node;
		else
			parent=flat(node.left);
		if(presentRightMost!=null)
		{
			presentRightMost.right=node;
			presentRightMost=null;
		}
		if(node.right==null)
			presentRightMost=node;
		else
			node.right=flat(node.right);
		return parent;
	}

}

using the next class which saves the root and leaf of each flatten BST :

public class NewTree {
	TreeNode head;
	TreeNode tail;
	
}

public class FlattenTree {
	public static void test()
	{
		System.out.println("Original:");
		TreeNode t= AssortedMethods.randomBST(5, 1,12);
		t.print();
		System.out.println("Flattened:");

		t=flatten(t);
		t.print();
	}

	private static TreeNode flatten(TreeNode t) {
		NewTree nt = flattenUtil(t);
		return nt.head;
	}

	private static NewTree flattenUtil(TreeNode t) {
		if(t==null)
			return null;
		NewTree left = flattenUtil(t.left);
		NewTree right = flattenUtil(t.right);
		NewTree ans = new NewTree();
		
		if(left!=null){
			ans.head=left.head;
			left.tail.right=t;
			t.left=null;
		}
		else
			ans.head=t;
		if(right!=null){
			ans.tail=right.tail;
			t.right= right.head;
		}
		else
			ans.tail=t;
		return ans;

	}
}

Traverse down the tree to find leaf nodes, once leaf nodes are available, put the root node all the way to the right of the left leaf and return the left leaf as the new root.

Node Flatten(Node root)
{
	if(root == null)
		return null;
	if(root.left == null && root.right == null)
		return root;

	Node left = Flatten(root.left);
	Node right = Flatten(root.right);

	root.right = right;

	if(left != null)
	{
		Node tmp = root;
		Node tmp2 = left;
		while(tmp2.right) tmp2 = tmp2.right;
		tmp2.right = tmp;
		tmp.left = null;
	}
	return left;
}

Approach : Using Inorder traversal...
1. Flatten the left subtree.
2. Flatten the right subtree.
3. Set the rightnode of root to flattened rightsubtree
4. Iterate through the flattened left subtree till the last element.
5. Set the right node of last element to root.

code

public BSTNode<T> flattenBinarySearchTree(BSTNode<T> root){
        if(root == null){
            return null;
        }
        if(root.getLeftNode() == null && root.getRightNode() == null){
            return root;
        }
        BSTNode<T> leftResult = flattenBinarySearchTree(root.getLeftNode());
        root.setRightNode(flattenBinarySearchTree(root.getRightNode()));
        BSTNode<T> currentNode = leftResult;
        while(currentNode!=null && currentNode.getRightNode()!=null){
            currentNode = currentNode.getRightNode();
        }
        currentNode.setRightNode(root);
        return leftResult;
    }

Can I rephrase the question? Traverse the tree and print out all the elements. That will flatten the tree into a linear array. A BST with only right children can be thought of as a linear.
For the example mentioned in the question, we can do a in-order traversal and get the desired result.