// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = (val===undefined ? 0 : val)
  this.left = (left===undefined ? null : left)
  this.right = (right===undefined ? null : right)
}

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
const printTree = (tree) =>{
  let queue = [tree]
  let height = 1
  while(queue.length){
    let next =[]
    let cals = queue.reduce((acc,curr)=>{
        acc= acc + ' '.repeat(40-height*10)+ curr.val
        return acc
    },'')
    console.log(cals);
    while(queue.length) {
      let val = queue.splice(0,1)[0]
      if(val.left) next.push(val.left)
      if(val.right) next.push(val.right)
      
    }
    if(next.length) {
      queue = next
      height++
    }
    
  }
}
var sortedArrayToBST = function(nums) {
    return createBst(nums, 0, nums.length-1)
};
const createBst= (arr, left, right) => {
    if(left>right) return null
    const mid = Math.ceil((left+right)/2)
    const root = new TreeNode(arr[mid])
    root.left = createBst(arr,left, mid-1)
    root.right = createBst(arr, mid+1, right)
    return root
}
const search = (bst, val)=>{
    if(bst.val === null) return null
    if(bst.val === val) return bst
    else if(bst.val > val) return search(bst.left, val)
    else return search(bst.right, val)
}
let a = [-1,0,2,3,6,10,20]
let tree = sortedArrayToBST(a)
printTree(tree)
printTree(search(tree,2))
// console.log(JSON.stringify(tree))