erika.r
BAN USERThe 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 }
}
}
Find the in-order successor of a node in a BST.
The first solution assumes each Node has a reference to its parent.
Node InOrderSucc(Node n) {
if (n == null)
return null; // or throw
// if there is a right child, the successor is the first element in an inorder traversal of that subtree
if (n.Right != null)
return LeftMostDescendant(n.Right);
// we must be the root, and without a right child, there is no successor
if (n.Parent == null)
return null;
// while n is a right child, it succedes its parent, so we go up
// if/when n is a left child, its parent will be its successor
// if we go up to the root without ever becoming a left child,
// it means the original n was the right-most element in the BST,
// and we will correctly return the root's parent - null
while (n.Parent.Right == n)
n = n.Parent;
return n;
}
private Node LeftMostDescendant(Node n) {
while (n.Left != null)
n = n.Left;
return n;
}
The second solution assumes that each node does not have a reference to its parent. and we are also given the root of the whole BST.
Node InOrderSucc(Node n, Node root) {
if (n == null)
return null; // or throw
// if there is a right child, the successor is the first element in an inorder traversal of that subtree
if (n.Right != null)
return LeftMostDescendant(n.Right);
var s = new Stack<Node>();
var m = root;
// find n, and push any node along the path to n onto the stack
while (m != null) {
if (m == n)
break;
s.push(m);
if m.Data < n.Data
m = m.Right;
else
m = m.Left;
}
// all n's parents are now on the stack
m = s.Peek() != null : s.Pop() : null;
while (m != null && n == m.Right) {
n = m;
m = s.Peek() != null ? s.Pop() : null;
}
return m;
}
private Node LeftMostDescendant(Node n) {
while (n.Left != null)
n = n.Left;
return n;
}
- erika.r July 21, 2015