ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Binary Search Tree Node Count

Special / Other

Goal -- WPM

Ready
Exercise Algorithm Area
1type TreeNode struct {

2Val   int

3Left  *TreeNode

4Right *TreeNode

5}

6

7// countNodesInBST recursively counts the number of nodes in a Binary Search Tree.

8// It traverses the tree and sums up the counts from the left and right subtrees.

9// This is a fundamental operation for understanding tree structures and their properties.

10// It's often a building block for other tree algorithms like finding height or depth.

11// The function handles the edge case of an empty tree gracefully.

12// It assumes a valid BST structure is provided.

13// The recursive approach is intuitive for tree traversals.

14// Each node is visited exactly once.

15// The base case ensures termination when an empty subtree is encountered.

16// This method is efficient for counting nodes.

17func countNodesInBST(root *TreeNode) int {

18// Base case: If the tree (or subtree) is empty, it has 0 nodes.

19if root == nil {

20return 0

21}

22

23// Recursive step: The total number of nodes is 1 (for the current node)

24// plus the number of nodes in the left subtree and the number of nodes

25// in the right subtree.

26leftCount := countNodesInBST(root.Left)

27rightCount := countNodesInBST(root.Right)

28

29return 1 + leftCount + rightCount

30}

31

32// Example usage (not part of the core function, for demonstration):

33// func main() {

34//     // Construct a sample BST:

35//     //      4

36//     //     / \

37//     //    2   5

38//     //   / \

39//     //  1   3

40//     root := &TreeNode{Val: 4}

41//     root.Left = &TreeNode{Val: 2}

42//     root.Right = &TreeNode{Val: 5}

43//     root.Left.Left = &TreeNode{Val: 1}

44//     root.Left.Right = &TreeNode{Val: 3}

45//

46//     nodeCount := countNodesInBST(root)

47//     fmt.Printf("Number of nodes in the BST: %d\n", nodeCount) // Output: 5

48//

49//     // Test with an empty tree

50//     var emptyRoot *TreeNode

51//     emptyCount := countNodesInBST(emptyRoot)

52//     fmt.Printf("Number of nodes in an empty BST: %d\n", emptyCount) // Output: 0

53// }
Algorithm description viewbox

Binary Search Tree Node Count

Algorithm description:

This function counts the total number of nodes in a Binary Search Tree (BST). It utilizes a recursive approach to traverse the tree. This is a fundamental operation for many tree-based algorithms and data analysis tasks, such as determining the size of a dataset represented by a BST or as a preliminary step for more complex tree operations.

Algorithm explanation:

The `countNodesInBST` function calculates the total number of nodes in a Binary Search Tree using recursion. The base case for the recursion is when the `root` pointer is `nil`, indicating an empty subtree, in which case it returns 0. For a non-empty subtree, the function returns 1 (for the current node) plus the result of recursively calling itself on the left child and the right child. This ensures that every node in the tree is visited exactly once. The time complexity is O(N), where N is the number of nodes in the tree, because each node is processed once. The space complexity is O(H) in the average case and O(N) in the worst case (for a skewed tree), where H is the height of the tree, due to the recursion call stack. The algorithm correctly handles an empty tree as an edge case.

Pseudocode:

function countNodesInBST(root):
  if root is null:
    return 0
  else:
    left_count = countNodesInBST(root.left)
    right_count = countNodesInBST(root.right)
    return 1 + left_count + right_count