wasnt nate

Interview Question: Process a Binary Tree

For this one the question was to walk a Binary Tree and call a method on the left then then right node. If there is any nodes to the left of the left that needs to be called first, and so on recursively.

To give a diagram assuming you started at at the top (node #4) this is the order that they should be called:
Binary Tree Call Order

The first step is to take and model this diagram; which becomes the following C# class:

class Node<T>
{
  public Node(T value)
  {
    Data = value;
  }

  public T Data { get; set; }
  public Node<T> Left { get; set; }
  public Node<T> Right { get; set; }

  public override string ToString()
  {
    return Data == null ? "null" : Convert.ToString(Data);
  }
}

Next a snippit was added to do the data entry

var head = new Node<int>(4);
var two = head.Left = new Node<int>(2);
two.Left = new Node<int>(1);
two.Right = new Node<int>(3);

var six = head.Right = new Node<int>(6);
six.Left = new Node<int>(5);
six.Right = new Node<int>(7);

Then a recursive method was created to do the simple processing.

public void OrderedExecuteRecursive(Action<T> callback)
{
  if (Left != null)
    Left.OrderedExecuteRecursive(callback);

  callback(Data);

  if (Right != null)
    Right.OrderedExecuteRecursive(callback);
}

Finally for a fun twist on this classic problem; walk the tree iteratively.

public void OrderedExecuteIterative(Action<T> callback)
{
  var stack = new Stack<Node<T>>();
  var processedNodes = new List<Node<T>>();

  if (this.Right != null)
    stack.Push(this.Right);

  var current = this;

  do
  {
    if (current.Left != null 
          && processedNodes.Contains(current.Left) == false)
    {
      stack.Push(current);
      current = current.Left;
      continue;
    }
    else
    {
      callback(current.Data);
      processedNodes.Add(current);
    }

    if (current.Right != null 
          && processedNodes.Contains(current.Right) == false)
    {
      current = current.Right;
      continue;
    }

    current = stack.Pop();
  } while (stack.Count > 0);
}

To verify that this is working as expected; here is the test code:

var expected = new List<int>(Enumerable.Range(1, 7));
var values = new List<int>();
head.OrderedExecuteRecursive(i => values.Add(i));

if (expected.Count != values.Count)
{
    Console.WriteLine("Wrong number of items returned");
}

for (var i = 0; i < expected.Count; i++)
{
    if (values[i] != expected[i])
    {
        Console.WriteLine("value[{0}] was incorrect");
    }
}

Leave a Reply