/**
 * Definition for binary tree
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    public TreeNode SortedArrayToBST(int[] num) {
        return _sortedArrayToBST(num, 0, num.Length - 1);
    }

    private TreeNode _sortedArrayToBST(int[] num, int lo, int hi){

        if(lo > hi) return null;

        var mid = lo + (hi - lo)/2;

        var root = new TreeNode(num[mid]);

        root.left = _sortedArrayToBST(num, lo, mid-1);
        root.right = _sortedArrayToBST(num, mid+1, hi);

        return root;

    }
}