Finding left and right heigth in Binary Search Tree

Question

How can I find the length of the path from the root to the deepest node in the tree for two side? I mean I can find the max height of the tree with height() method as below code. I can find max height with that code line1 + Math.max(this._height(root.getleft()), this._height(root.getright())). There is any way to find height of left side and height of right side. Thanks,

const inputString1 = `13
    25
    39
    12
    19
    9
    23
    55
    31
    60
    35
    41
    70
    90`;
    //left 3 right 5
    const inputLines1: string[] = inputString1.split("\n");
    let leftHeight = 0;
    let rightHeight = 0;
    let currentLine1: number = 0;
    function readLine1(): string {
      return inputLines1[currentLine1++];
    }
    
    class TreeNode1<T> {
      private _value: T;
      public getvalue(): T {
        return this._value;
      }
      public setvalue(v: T) {
        this._value = v;
      }
    
      private _left: TreeNode1<T>;
    
      public getleft(): TreeNode1<T> {
        return this._left;
      }
    
      public setleft(node: TreeNode1<T>) {
        this._left = node;
      }
    
      private _right: TreeNode1<T>;
    
      public getright(): TreeNode1<T> {
        return this._right;
      }
    
      public setright(node: TreeNode1<T>) {
        this._right = node;
      }
    
      constructor(value: T) {
        this._value = value;
        this._left = null as any;
        this._right = null as any;
      }
    }
    
    class BinarySearchTree1<T> {
      leftHeight:number=0;
      rightHeight:number=0;
      height() {
        return this._height(this._root);
      }
    
      _height(root?: TreeNode1<T>): any {
        if (!root || (root.getleft() == null && root.getright() == null)) {
          return 0;
        }
    
        return (
          1 + Math.max(this._height(root.getleft()), this._height(root.getright()))
        );
      }
    
      private _root: TreeNode1<T>;
      public getroot(): TreeNode1<T> {
        return this._root;
      }
    
      public setroot(v: TreeNode1<T>) {
        this._root = v;
      }
      constructor() {
        this._root = null as any;
      }
    
      addToTree(v: T): boolean | undefined {
        const newNode = new TreeNode1(v);
        if (this._root == null) {
          this._root = newNode;
          return true;
        } else {
          let currentNode = this.getroot();
          let traversing = true;
          while (traversing) {
            if (currentNode != null) {
              if (currentNode.getvalue() == newNode.getvalue()) {
                traversing = false;
                return false;
              } else if (currentNode.getvalue() > newNode.getvalue()) {
                if (currentNode.getleft() == null) {
                  currentNode.setleft(newNode);
                  traversing = false;
                  return true;
                } else {
                  currentNode = currentNode.getleft();
                }
              } else {
                if (currentNode.getright() == null) {
                  currentNode.setright(newNode);
                  traversing = false;
                  return true;
                } else {
                  currentNode = currentNode.getright();
                }
              }
            }
          }
        }
      }
    
      BFS(): T[] {
        let queue = new Array<TreeNode1<T>>();
        let visited = new Array<T>();
        queue.push(this._root);
        while (queue.length != 0) {
          let currentNode = queue.shift();
          if (currentNode !== null) {
            visited.push(currentNode!!.getvalue());
          }
    
          if (currentNode !== null) {
            if (currentNode!!.getleft() !== null)
              queue.push(currentNode!!.getleft());
            if (currentNode!!.getright !== null)
              queue.push(currentNode!!.getright());
          }
        }
        return visited;
      }
    }
    
    function main1() {
      let myBST = new BinarySearchTree1<number>();
      for (let i = 1; i < inputLines1.length; i++) {
        myBST.addToTree(Number(inputLines1[i]));
      }
      console.log("BFS: " + myBST.BFS(), myBST.height());
      console.log(leftHeight, rightHeight);
    }
    
    main1();

Answer 1

First of all, the height of a tree that has no nodes, is -1, as can be read on Wikipedia:

Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.

So your height method should be corrected to:

  _height(root?: TreeNode1<T>): number {
    if (!root) {
      return -1;
    }
    return (
      1 + Math.max(this._height(root.getleft()), this._height(root.getright()))
    );
  }

Then, remove the leftHeight and rightHeight members, and instead make them methods:

  leftHeight(): number {
    if (!this._root) {
      return -2;
    }
    return this._height(this._root.getleft());
  }
  rightHeight(): number {
    if (!this._root) {
      return -2;
    }
    return this._height(this._root.getright());
  }

...and call them in your main function.