export const isBinaryTree = < T > ( t ) : t is LeafonlyBinaryTree < T > => { return t instanceof LeafonlyBinaryTree ; } ; export type NestedPairs < T > = [ T | NestedPairs < T > , T | NestedPairs < T > ] ; export const isNestedPair = ( nestedPair ) : nestedPair is NestedPairs < unknown > => { return typeof nestedPair === 'object' ; } ; export type BinarySide = 'left' | 'right' ; export type BinaryTreeSide < T > = { value ? : T ; tree ? : LeafonlyBinaryTree < T > ; } ; /**
 * Compared to a normal Binary tree where nodes have three values:
 * left?: Node<T>;
 * value: T;
 * right?: Node<T>;
 * This trees nodes doesn't have a value field. Instead each side is either
 * another node or a value. (In the implementation it's split for convenience)
 * left: Node<T> | T;
 * right: Node<T> | T;
 * Because of this reason, it only stores values
 */ export class LeafonlyBinaryTree < T = number > { public parent ? : LeafonlyBinaryTree < T > ; public parentSide ? : BinarySide ; public leftTree ? : LeafonlyBinaryTree < T > ; public leftValue ? : T ; public rightTree ? : LeafonlyBinaryTree < T > ; public rightValue ? : T ; constructor ( left , right ) { if ( left instanceof LeafonlyBinaryTree ) { this . leftTree = left ; this . leftTree . parent = this ; this . leftTree . parentSide = 'left' ; } else { this . leftValue = left ; } if ( right instanceof LeafonlyBinaryTree ) { this . rightTree = right ; this . rightTree . parent = this ; this . rightTree . parentSide = 'right' ; } else { this . rightValue = right ; } } set left ( left ) { if ( left instanceof LeafonlyBinaryTree ) { this . leftTree = left ; this . leftTree . parent = this ; this . leftTree . parentSide = 'left' ; this . leftValue = undefined ; } else { this . leftValue = left ; this . leftTree = undefined ; } } get left ( ) : LeafonlyBinaryTree < T > | T { return this . leftTree ?? this . leftValue ! ; } set right ( right ) { if ( right instanceof LeafonlyBinaryTree ) { this . rightTree = right ; this . rightTree . parent = this ; this . rightTree . parentSide = 'right' ; this . rightValue = undefined ; } else { this . rightValue = right ; this . rightTree = undefined ; } } get right ( ) : LeafonlyBinaryTree < T > | T { return this . rightTree ?? this . rightValue ! ; } getSide ( side ) { return side === 'left' ? this . left : this . right ; } setSide ( side , value ) { if ( side === 'left' ) { this . left = value ; } else { this . right = value ; } } inOrderSuccessor ( ) { if ( this . rightTree ) { return this . rightTree . leftMostTree ( ) ; } else { let node = this as LeafonlyBinaryTree < T > ; while ( node . parent && node . parentSide !== 'left' ) { node = node . parent ; console . log ( 'inOrderSuccessor ascend' , node . toString ( ) , node . parent ?. toString ( ) ) ; } if ( node . parent ?. rightTree ) { node = node . parent . rightTree ; console . log ( 'inOrderSuccessor jump' , node . toString ( ) ) ; } while ( node . leftTree ) { node = node . leftTree ; console . log ( 'inOrderSuccessor descend' , node . toString ( ) ) ; } return node ; } } inOrderPredecessor ( ) { if ( this . leftTree ) { return this . leftTree . rightMostTree ( ) ; } else { let node = this . parent as LeafonlyBinaryTree < T > ; while ( node . parent && node . parentSide !== 'right' ) { node = node . parent ; console . log ( 'inOrderPredecessor ascend' , node . toString ( ) , node . parent ?. toString ( ) ) ; } if ( node . parent ?. leftTree ) { node = node . parent . leftTree ; console . log ( 'inOrderPredecessor jump' , node . toString ( ) ) ; } while ( node . rightTree && node . rightTree !== node ) { console . log ( 'predescent' , node . toString ( ) , node . rightTree . toString ( ) ) ; node = node . rightTree ; console . log ( 'inOrderPredecessor descend' , node . toString ( ) ) ; } return node ; } } inOrderSuccessorBad ( ) { if ( this . rightTree ) { console . log ( 'asd' ) ; return this . rightTree . leftMostTree ( ) ; } console . log ( '2asd' ) ; let node = this as LeafonlyBinaryTree < T > ; let next = node . parent ; while ( next && node === next . rightTree ) { node = next ; next = next . parent ; } return next ?. rightTree ?. leftMostTree ( ) ; } inOrderPredecessorBad ( ) { if ( this . leftTree ) { return this . leftTree . rightMostTree ( ) ; } let node = this as LeafonlyBinaryTree < T > ; let next = node . parent ; while ( next != null && node === next . leftTree ) { node = next ; next = next . parent ; } return next ?. leftTree ?. rightMostTree ( ) ; } leftMostTree ( ) { let next = this as LeafonlyBinaryTree < T > ; while ( next . leftTree ) { next = next . leftTree ; } return next ; } rightMostTree ( ) { let next = this as LeafonlyBinaryTree < T > ; while ( next . rightTree ) { next = next . rightTree ; } return next ; } replace ( next ) { if ( this . parent ) { if ( this . parentSide === 'right' ) { this . parent . right = next ; } else { this . parent . left = next ; } } this . leftValue = 999 ; this . rightValue = 999 ; } get root ( ) : LeafonlyBinaryTree < T > { let parent = this . parent ?? this ; while ( parent ?. parent ) { parent = parent . parent ; } return parent ; } get depth ( ) : number { return 1 + ( this . parent ?. depth ?? 0 ) ; } static fromNestedPairs < T > ( nestedPairs ) { let left ; let right ; if ( isNestedPair ( nestedPairs ) ) { if ( isNestedPair ( nestedPairs [ 0 ] ) ) { left = LeafonlyBinaryTree . fromNestedPairs ( nestedPairs [ 0 ] ) ; } else { left = nestedPairs [ 0 ] ; } if ( isNestedPair ( nestedPairs [ 1 ] ) ) { right = LeafonlyBinaryTree . fromNestedPairs ( nestedPairs [ 1 ] ) ; } else { right = nestedPairs [ 1 ] ; } } else { throw new Error ( 'not a full binary tree source' ) ; } return new LeafonlyBinaryTree < T > ( left , right ) ; } public * leftToRight ( ) { if ( this . leftTree ) { yield * this . leftTree . leftToRight ( ) ; } else if ( this . leftValue ) { yield this . leftValue ; } if ( this . rightTree ) { yield * this . rightTree . leftToRight ( ) ; } else if ( this . rightValue ) { yield this . rightValue ; } } private * rightToLeft ( ) { if ( this . rightTree ) { yield * this . rightTree . rightToLeft ( ) ; } else if ( this . rightValue ) { yield this . rightValue ; } if ( this . leftTree ) { yield * this . leftTree . rightToLeft ( ) ; } else if ( this . leftValue ) { yield this . leftValue ; } } toString ( ) { const leftString = this . leftTree ? this . leftTree . toString ( ) : this . leftValue ; const rightString = this . rightTree ? this . rightTree . toString ( ) : this . rightValue ; return `[${ leftString },${ rightString }]` ; } print ( ) { console . log ( this . toString ( ) ) ; } }