Merging Two Binary Search Trees in O(logn) Space

main.cpp

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <stack>

#include "Node.hpp"
#include "NodeStream.hpp"
#include "MergeNodeAlgorithm.hpp"
#include "MergeNodeStream.hpp"
#include "MergeNodeVector.hpp"


using namespace std;


static Node<int>* randomTree(size_t depth, int lo, int hi) {
  if (!depth) return NULL;
  int data = lo + rand() % (hi - lo + 1);
  return new Node<int>(
    data,
    randomTree(depth-1, lo, data),
    randomTree(depth-1, data, hi));
}


static void validate(
  const Node<int>* lhn,
  const Node<int>* rhn,
  MergeNodeAlgorithm<int>& mna) {
  bool error = false;
  if (!mna.empty())
    for (int prev = mna.get(); !mna.empty(); prev = mna.get(), mna.pop())
      if (prev > mna.get()) {
        error = true;
        cout << "[ERROR] prev: " << prev << ", curr: " << mna.get() << endl;
      }
  if (error) {
    cout << "lhn: " << *lhn << endl;
    cout << "rhn: " << *rhn << endl;
  }
}


int main(int argc, char *argv[]) {
  if (argc != 2 && argc != 3) {
    cerr << "Usage: " << argv[0] << " <DEPTH> [<USE-STREAM>]" << endl;
    exit(1);
  }
  size_t depth = atoi(argv[1]);
  bool useStream = argc == 2;

  srand(time(NULL));
  Node<int>* lhn = randomTree(depth, 0, RAND_MAX);
  Node<int>* rhn = randomTree(depth, 0, RAND_MAX);

  if (useStream) {
    NodeStream<int> lhs(lhn);
    NodeStream<int> rhs(rhn);
    MergeNodeStream<int> mns(lhs, rhs);
    validate(lhn, rhn, mns);
  } else {
    MergeNodeVector<int> mnv(lhn, rhn);
    validate(lhn, rhn, mnv);
  }

  delete lhn;
  delete rhn;

  return 0;
}

MergeNodeAlgorithm.hpp

#ifndef MERGE_NODE_ALGORITHM_HPP
#define MERGE_NODE_ALGORITHM_HPP


template <class T>
class MergeNodeAlgorithm {
public:
  virtual bool empty() const = 0;
  virtual void pop() = 0;
  virtual T get() const = 0;
};


#endif

MergeNodeStream.hpp

#ifndef MERGE_NODE_STREAM_HPP
#define MERGE_NODE_STREAM_HPP


template <class T>
class MergeNodeStream : public MergeNodeAlgorithm<T> {
public:
  MergeNodeStream(NodeStream<T>&, NodeStream<T>&);
  bool empty() const;
  void pop();
  T get() const;

private:
  NodeStream<T>& _xs;
  NodeStream<T>& _ys;
};


template <class T>
MergeNodeStream<T>::MergeNodeStream(NodeStream<T>& xs, NodeStream<T>& ys)
  : _xs(xs), _ys(ys) {}


template <class T>
bool MergeNodeStream<T>::empty() const {
  return _xs.empty() && _ys.empty();
}


template <class T>
void MergeNodeStream<T>::pop() {
  if (!_xs.empty() && !_ys.empty()) {
    NodeStream<T>& smallest = _xs.get() < _ys.get() ? _xs : _ys;
    smallest.pop();
  }

  if (_xs.empty() || _ys.empty()) {
    NodeStream<T>& nonempty = _xs.empty() ? _ys : _xs;
    nonempty.pop();
  }
}


template <class T>
T MergeNodeStream<T>::get() const {
  if (!_xs.empty() && !_ys.empty()) {
    NodeStream<T>& smallest = _xs.get() < _ys.get() ? _xs : _ys;
    return smallest.get();
  }

  if (_xs.empty() || _ys.empty()) {
    NodeStream<T>& nonempty = _xs.empty() ? _ys : _xs;
    return nonempty.get();
  }

  return NULL;
}


#endif

MergeNodeVector.hpp

#ifndef MERGE_NODE_VECTOR_HPP
#define MERGE_NODE_VECTOR_HPP


template <class T>
class MergeNodeVector : public MergeNodeAlgorithm<T> {
public:
  MergeNodeVector(const Node<T>*, const Node<T>*);
  ~MergeNodeVector();
  bool empty() const;
  void pop();
  T get() const;

private:
  NodeStream<T>* _lhs;
  int* _rhv;
  size_t _nrh;
  size_t _rhp;
};


template <class T>
MergeNodeVector<T>::MergeNodeVector(const Node<T>* lhn, const Node<T>* rhn) {
  assert(lhn && rhn);
  _lhs = new NodeStream<T>(lhn);
  _rhp = 0;
  _nrh = rhn->size();
  _rhv = new int[_nrh];
  NodeStream<int> rhs(rhn);
  for (size_t i = 0; i < _nrh; ++i) {
    _rhv[i] = rhs.get();
    rhs.pop();
  }
}


template <class T>
MergeNodeVector<T>::~MergeNodeVector() {
  delete _lhs;
  delete _rhv;
}


template <class T>
bool MergeNodeVector<T>::empty() const {
  return _lhs->empty() && _rhp == _nrh;
}


template <class T>
void MergeNodeVector<T>::pop() {
  if (!_lhs->empty() && _rhp < _nrh) {
    if (_rhv[_rhp] < _lhs->get())
      _rhp++;
    else
      _lhs->pop();
  }
  else if (!_lhs->empty())
    _lhs->pop();
  else if (_rhp < _nrh)
    _rhp++;
}


template <class T>
T MergeNodeVector<T>::get() const {
  if (!_lhs->empty() && _rhp < _nrh) {
    if (_rhv[_rhp] < _lhs->get())
      return _rhv[_rhp];
    else
      return _lhs->get();
  }

  if (!_lhs->empty())
    return _lhs->get();

  if (_rhp < _nrh)
    return _rhv[_rhp];

  return NULL;
}


#endif

Node.hpp

#ifndef NODE_HPP
#define NODE_HPP


template <class T>
class Node {
public:
  Node(T);
  Node(T, Node<T>*, Node<T>*);
  T data() const;
  Node<T>* left() const;
  Node<T>* right() const;
  size_t size() const;
  ~Node();

private:
  T _data;
  Node<T>* _left;
  Node<T>* _right;
};


template <class T>
Node<T>::Node(T data) : _data(data), _left(NULL), _right(NULL) {}


template <class T>
Node<T>::Node(T data, Node<T>* left, Node<T>* right)
  : _data(data), _left(left), _right(right) {}


template <class T>
T Node<T>::data() const { return _data; }


template <class T>
Node<T>* Node<T>::left() const { return _left; }


template <class T>
Node<T>* Node<T>::right() const { return _right; }


template <class T>
size_t Node<T>::size() const {
  size_t size = 1;
  if (_left) size += _left->size();
  if (_right) size += _right->size();
  return size;
}


template <class T>
Node<T>::~Node() {
  if (_left) delete _left;
  if (_right) delete _right;
}


template <class T>
std::ostream& operator<<(std::ostream& stream, const Node<T>& node) {
  if (node.left() && node.right())
    return stream
      << "Node("
      << *node.left() << ", "
      << node.data() << ", "
      << *node.right() << ")";
  else if (node.left())
    return stream
      << "Node("
      << *node.left() << ", "
      << node.data() << ", X)";
  else if (node.right())
    return stream
      << "Node(X, "
      << node.data() << ", "
      << *node.right() << ")";
  else
    return stream << "Node("<< node.data() << ")";
}


#endif

NodeStream.hpp

#ifndef NODE_STREAM_HPP
#define NODE_STREAM_HPP


template <class T>
class NodeStream {
public:
  NodeStream(const Node<T>*);
  bool empty() const;
  void pop();
  T get() const;

private:
  std::stack<const Node<T>*> nodes;
  void consume(const Node<T>*);
};


template <class T>
NodeStream<T>::NodeStream(const Node<T>* root) {
  consume(root);
}


template <class T>
bool NodeStream<T>::empty() const {
  return nodes.empty();
}


template <class T>
void NodeStream<T>::pop() {
  const Node<T>* node = nodes.top();
  nodes.pop();
  consume(node->right());
}


template <class T>
T NodeStream<T>::get() const {
  return nodes.top()->data();
}


template <class T>
void NodeStream<T>::consume(const Node<T>* root) {
  if (root) {
    nodes.push(root);
    consume(root->left());
  }
}


#endif

TreeMerge.scala

import Ordering.Implicits._

case class Tree[T: Ordering](data: T, left: Option[Tree[T]] = None, right: Option[Tree[T]] = None) {
  def this(data: T) = this(data, None, None)

  def stream: Stream[T] = this match {
    case Tree(d, Some(l), Some(r)) => l.stream ++ Stream.cons(data, r.stream)
    case Tree(d, Some(l), None)    => l.stream :+ d
    case Tree(d, None,    Some(r)) => d +: r.stream
    case Tree(d, None,    None)    => Stream(d)
  }

  def merge(that: Tree[T]): Stream[T] = {
    def reduce(xs: Stream[T], ys: Stream[T]): Stream[T] = {
      if      (xs.isEmpty)        ys
      else if (ys.isEmpty)        xs
      else if (xs.head < ys.head) xs.head +: reduce(xs.tail, ys)
      else                        ys.head +: reduce(xs, ys.tail)
    }
    reduce(this.stream, that.stream)
  }
}

val xs = Tree(3, Some(Tree(2)), Some(Tree(6)))
val ys = Tree(4, Some(Tree(1)), Some(Tree(5)))
println(xs.merge(ys).force)