Decision Tree and Recursion

A decision tree can be implemented recursively by branching left or right at each node based on a decision criteria. Recursion allows elegantly expressing the tree traversal logic.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
boolean decisionTree(TreeNode root, int value) {
  if (root == null) return false; 
  if (root.data == value) return true;
  
  // Recurse left
  if (value < root.data) {
    return decisionTree(root.left, value);
  } 
  // Recurse right
  else {
    return decisionTree(root.right, value);
  }
}

C++ example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
bool decisionTree(TreeNode* root, int value) {
  if (root == NULL) return false;
  if (root->data == value) return true;

  if (value < root->data) {
    return decisionTree(root->left, value); 
  } else {
    return decisionTree(root->right, value);
  }
}

Python example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def decisionTree(root, value):
  if root is None: 
    return False
  if root.data == value:
    return True 
  
  if value < root.data:
    return decisionTree(root.left, value)
  else:
    return decisionTree(root.right, value)

The key ideas are:

Base cases for null node and matching value
Recursively search left/right subtree based on criteria
Avoid duplicate traversal logic with recursion

Recursion provides an elegant way to traverse decision tree structures. Useful for machine learning classification and predictions.