Core Tree Terminologies

A Tree is a connected, acyclic, and hierarchical data structure consisting of nodes. One node is designated as the root, and every other node is connected by exactly on path from the root. Each node may have zero or more children, but exactly on parent (except for the root).

Key Properties of a Tree

A Node is a fundamental unit in a tree that holds data and can link to other nodes (children). Each node may contain a value, reference(s) to child node(s), and sometimes a reference to the parent.

An Edge is a connection or link between two nodes (typically from a parent to a child). In a tree with N nodes, there are exactly N - 1 edges.

A Root is the topmost node in a tree hierarchy. It has no parent. All other nodes descend from the root. A tree can have only one root.

A Leaf is a node that has no children. It is at the bottom of the tree structure. Also known as a terminal node.

A Parent is a node that has one or more children connected to it. It provides a link downward in the hierarchy.

A Child is a node that descends from another node. A child has exactly on parent (except in DAGs or general graphs).

Height is the length of the longest path from a node to a leaf. The height of a tree is the height of its root node.

Depth is the distance from the root to a given node (i.e., the number of edges in the path from root to that node). Root has depth 0.

Subtree is a subset of another tree. It consists of a node and all its descendants.

Degree of node is the number of children a node has. The degree of a tree is the maximum degree among all nodes in the tree.

Types of Trees

1. Binary Tree: A tree in which each node has at most two children, referred to as the left and right child.

Foundational for more specialized trees like BSTs, heaps, and segment trees.

2. Binary Search Tree (BST): A special type of binary tree that maintains a sorted order.

• All nodes in the left subtree have values less than the node.
• All nodes in the right subtree have values greater than the node.

Supports efficient searching, insertion, and deletion in O log n average time if balanced.

3. N-ary Tree: A tree in which can have any number of children.

Organizational charts, file systems, XML/HTML parsers, AI game trees.

If children N = 2, it becomes a binary tree.

4. Balanced Tree: A tree where the height difference between left and right subtrees for any node is at most 1 (in AVL), or height is kept logarithmic relative to the number of nodes.

Ensure O log n time complexity for operations.

5. Unbalanced Tree A tree where the height can become skewed and not logarithmic, leading to degraded performance.

Preorder Traversal

1. Given the root of a binary tree, Design an algorithm that returns a list containing the values of all nodes visited in preorder traversal order, which follows the sequence: Root -> Left -> Right.

Binary Tree Node:

  class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
                   

Inorder Traversal

2. Given the root of a binary tree. Design an algorithm that will return the inorder traversal of its nodes values.

Inorder traversal follows the pattern: Left -> Root -> Right.

Binary Tree Node:

    class TreeNode {
        constructor(value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

Postorder Traversal

3. Given a binary tree. Design an algorithm that returns the values of its nodes in postorder traversal order (Left -> Right -> Root).

Binary Tree Node:

    class TreeNode {
        constructor(value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

Level Order Traversal

4. Given the root of a binary tree. Design an algorithm that returns the values of its nodes level by level (breadth-first traversal), from top to bottom, left to right.

Return a 2D array where each subarray contains the node values at that specific level.

 class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Depth of Tree

5. Given a binary tree. Design an algorithm that returns the height of the tree.

A binary tree height is the number of levels it contains, where the root is at level 1 and height is the total number of levels from the root to the deepest leaf node.

   class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }

Is it a BST?

6. Given the root of a binary tree. Design an algorithm that determines if the tree is a valid Binary Search Tree(BST).

A valid BST is defined as:

• The left subtree of a node contains only nodes with values less than the nodes value.
• The right subtree of a node contains only nodes with values greater than the nodes value.
• Both the left and right subtrees must also be valid BSTs.

Return true if it is a valid BST, otherwise return false.

   class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }

Size of the Binary Tree

7. Given the root of a binary tree. Design an algorithm that will return the total number of nodes in the binary tree.

 class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
 }

Count Leaf Nodes

8. Given the root of a Binary Tree. Design an algorithm that returns the total number of leaf nodes in the tree.

A leaf node is a node with no children - both its left and right pointers are null.

Spiral Level Traversal

9. Given the root node of a binary tree. Design an algorithm that return the level order traversal in spriral (zigzag) form.

• Start from the root at level 0.
• Traverse left to right on even-numbered levels.
• Traverse right to left on odd-numbered levels.

Return a 2D array where each subarray contains node values for the level.

   class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }

Mirror Binary Tree

10. Design an algorithm to invert a binary tree such that the tree becomes a mirror image of itself.

For every node its left and right children must be swapped.

Return the root node of the mirrored tree.

   class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }

Identical Binary Trees

11. Given the roots of two binary trees. Design an algorithm that checks if they are structurally identical and nodes have the same value.

Return true if the trees are identical, otherwise return false.

    class TreeNode {
     constructor(value) {
       this.value = value;
       this.left = null;
       this.right = null;
     }
   }
 
 

Diameter of a Binary tree

12. Given the root of a binary tree. Design an algorithm that return the length (number of edges) of the longest path between any two nodes in the tree.

   class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }

Lowest Common Ancestor

13. Given the root of a binary tree and two distinct nodes p and q. Design an algorithm that return their lowest common ancestor (LCA).

The Lowest Common Ancestor of two nodes p and q in a binary tree is defined as the deepest node (i.e., farthest from the root) that is an ancestor of both p and q.

Note: A node can be a descendant of itself according to the definition of ancestor.

   class TreeNode {
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }

Construct Binary Tree 1

1. Given two integer arrays:

• preorder[] which represents the preorder traversal of a binary tree (Root -> Left -> Right)
• inorder[] which represents the inorder traversal of the same binary tree (Left -> Root -> Right)

Both arrays contain unique elements and represent the traversal of a valid binary tree.

Design an algorithm to construct the binary tree and return its root node.

You may assume that the tree contains no duplicate values.

 class TreeNode {
   constructor(value) {
   this.value = value;
   this.left = null;
   this.right = null;
   }
 }

Construct Binary Tree 2

2. Given Two integer arrays:

• postorder[] represents the postorder traversal of a binary tree (Left -> Right -> Root)
• inorder[] represents the inorder traversal of the same binary tree (Left -> Root -> Right)

Both arrays contain unique elements, and the tree is guaranteed to be valid.

Design an algorithm that constructs the binary tree and returns the root node of the tree.

You may assume that the tree contains no duplicate values.

 class TreeNode {
   constructor(value) {
   this.value = value;
   this.left = null;
   this.right = null;
   }
 }

Serializing Deserializing Tree

Serialization is the process of converting a binary tree into a string representation that can be easily stored or transmitted.

Deserializing is the inverse process, where the string is used to reconstruct the original binary tree.

3. Design an algorithm that implement the following two functions:

• serialize(root) - Encodes a tree to a single string.
• deserialization - is the inverse process, where the string is used to reconstruct the original binary tree.

The algorithm should:

• Preserve Structure and Values: The serialized string must retain the exact structure and values of the original tree.
• Handle null (missing) children which is represented as '#' correctly.
• Work for large and skewed trees efficiently.

Assume all node values are integers and the binary tree does not contain cycles.

 class TreeNode {
   constructor(value) {
   this.value = value;
   this.left = null;
   this.right = null;
   }
 }

Is Binary Tree Balanced?

4. Given the root of a binary tree. Design an algorithm that determine whether the tree is height-balanced.

A binary tree is height-balanced if, for every node in the tree, the absolute difference between the heights of the left and right subtrees is no more than 1, and both subtrees are also height-balanced.

Return: true if the tree is height-balanced, otherwise return false.

    class TreeNode {
      constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
      }
    }
   

Path with Maximum Sum

5. Given the root of a binary tree where each node contains an integer value (positive, negative, or zero).

A path is defined as any sequence of connected nodes in the tree where:

• Each pair of adjacent nodes is connected by a parent-child link.
• Each node in the path appears only once.
• The path can start and end at any node in the tree.

The sum of a path is the sum of the values of the nodes in that path.

Design an algorithm that computes the maximum path sum and return the maximum sum of values along any valid path.

  class TreeNode {
    constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    }
  }
 

Root to Leaf Path Sum Finder

6. Given the root of a binary tree where each node contains an integer value, and an integer targetSum.

Design an algorithm that finds all root-to-leaf path in the tree such that the sum of the node values in each path equals targetSum.

A root-to-leaf path is defined as a path starting from the root node and ending at a leaf node (i.e., a node with no children).

Return a list of all valid paths, where each path is represented as a list of integers.

Boundary Traversal of a Binary Tree

7. Given a root of a binary tree. Design an algorithms that returns the boundary raversal of the tree in anti-clockwise order, starting from the root.

The boundary includes three parts:

• Left Boundary - all the nodes on the left edge, excluding leaf nodes.
• Leaf nodes - all the leaf nodes (from left to right).
• Right Boundary - all the nodes on the right edge, excluding leaf nodes, collected in reverse order.

Return a list of node values representing the boundary traversal in the specified order.

  class TreeNode {
      constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }
     

Vertical Order Traversal

8. Given the root of a binary tree. Design an algorithm that returns the vertical order traversal of its nodes values.

For vertical traversal:

• Each node is assigned a horizontal distance (HD) from the root. The root has HD = 0. Left child has HD-1, and right child has HD + 1.
• Nodes are grouped by their horizontal distance (HD) from the root.
• Within the same column, nodes are ordered top-to-bottom by depth (level).
• If multiple nodes share the same column and depth, they should appear in left-to-right order, i.e., as encountered in a level-order (BFS) traversal.

Return a list of lists, where each sublist represents a vertical level from leftmost to rightmost.

  class TreeNode {
      constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
  }
     

Delete a Node in BST

9. Given the root of a Binary Search Tree and an integer key. Design an algorithms to delete the node with the given key in the BST while preserving the BST properties.

Return the root node of the updated BST after deletion.

BST Properties to Preserve:

• The left subtree of a node contains only nodes with values less than the node's value.
• The right subtree of a node contains only nodes with values greater than the node's value.
• Both left and right subtrees must also be BSTs.

Kth Smallest Element in BST

10. Given the root of a binary search tree (BST) and an integer k. Design an algorithm to find and return the kth smallest element in the BST.

The BST contains unique values and follows the standard properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.

1 ≤ k ≤ total number of nodes in the tree.

LCA in BST

11. Given the root of a Binary Search Tree(BST) and two nodes p and q (existing in the tree). Design an algorithm to find and return their lowest common ancestor (LCA).

The Lowest Common Ancestor of two nodes p and q in a BST is defined as the lowest(i.e., deepest) node in the tree that has both p and q as decendants (where a node can be a descendant of itself).

• All node values in the BST are unique.
• Both nodes p and q are guaranteed to exist in the tree.