Google Round 3 Cord Tree

// In computer programming, a cord is a data structure composed of smaller strings that is used to efficiently store and manipulate a very long string. For example, a text editing program may use a cord to represent the text being edited, so that operations such as insertion, deletion, and random access can be done efficiently.
// The string is broken up and stored in a tree. The tree has two types of nodes. There is a leaf node which will contain a length field and a data field. There is also an internal node which stores a pointer to a left child and a
// pointer to a right child. The internal node stores the total length of its two children.
  
// Some examples
// -------------

// * A single leaf:
//   root: Leaf<len=5>:ABCDE

// * A larger tree:
//   root: Internal<len=26>
//       ->left : Leaf<len=5>:ABCDE
//       ->right: Internal<len=21>
//           ->left : Leaf<len=10>:FGHIJKLMNO
//           ->right: Leaf<len=11>:PQRSTUVWXYZ



// 1) Define the structures, in code, for these two node types.
  
 Public Node {
    String text;
    boolean isLeaf;
    int length;
    Node left;
    Node right;
  
    public Node(int length, Node left, Node right) {
      this.text = "";
      this.isLeaf = false;
      this.length = length;
      this.left = left;
      this.right = right;
    }
  
    public Node(String text, int length) {
      this.text = text;
      this.isLeaf = true;
      this.length = length;
    }  
}

// 2) Write a function that accepts a cord and an index N. Return the Nth character in the cord.

public char getChar(Node root, int n) {
  if (n > root.length || n <= 0) {
    throw new InvalidRequestException("Out of bound");
  }
  if (root.isLeaf) {
    return root.text.charAt(n-1);
  }
  
  if (root.left != null || root.left.length >= n) 
    return getChar(root.left, n);
  
  if (root.right != null || root.right.length < n) 
    return getChar(root.right, n - root.left.length);  
  
  throw new InvalidRequestException("Invalid State");
}


// 3) Implement a function that accepts a cord, an index N, and a length L.
// Return a string that represents the cord contents from [N, N+L). E.g., if
// N = 3, L = 5, then return "DEFGH".


// * A larger tree:
//   root: Internal<len=26>
//       ->left : Leaf<len=5>:ABCDE
//       ->right: Internal<len=21>
//           ->left : Leaf<len=10>:FGHIJKLMNO
//           ->right: Leaf<len=11>:PQRSTUVWXYZ       
          
public String getString(Node root, int n, int l) {
  int start = n, end = n + l; // start = 3, end = 8
  
  if (start > root.length || end > root.length || start <= 0 ) {
    throw new InvalidRequestException("Out of bound");
  }
  if (root.isLeaf) {
    return root.text.substring(Math.max(start-1, root.text.length), Math.min(root.text.length, end));
  }
  
  StringBuilder sb = new StringBuilder();
  
  if (root.left != null && root.left.length >= start) 
    sb += getString(root.left, start, end);
  
  if (root.right != null && end > left.text.length) 
    sb += getString(root.right, start - left.text.length, end - root.left.length);  
  
  return sb.toString();
}