Binary search trees (Coding for Interviews)

tree.c

/*
 * Question 1: The three main depth-first traversals are:
 * preorder: visiting the root, then left and right subtree,
 * inorder: visiting the left subtree, then root, then right subtree
 * postorder: visiting the left and right subtree, then the root
 *
 * In implementing any of these, you just want to make sure you hit 
 * every node and that you don't try to visit NULL nodes
 */

#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

// binary tree structure, just using int for data at each node
struct tree_node {
  struct tree_node *left;
  struct tree_node *right;
  int data;
};
typedef struct tree_node* tree;

// allocates for a new tree
tree tree_new(int data){
  tree t = malloc(sizeof(struct tree_node));
  t->left = NULL;
  t->right = NULL;
  t->data = data;
  return t;
}

// free all nodes in a tree
void tree_free(tree t){
  if(t == NULL) return;
  tree_free(t->left);
  tree_free(t->right);
  free(t);
}

// sample "visit" function (can do anything here)
// included "depth" argument for printing purposes
void visit(tree t, int depth){
  while(depth > 0){
21depth--;
	printf("-");
  }
  printf("%d\n", t->data);
}

// visit a tree preorder
void preorder(tree t, int depth){
  if(t == NULL) return;
  visit(t, depth);
  preorder(t->left, depth + 1);
  preorder(t->right, depth + 1);
}

// visit a tree inorder
void inorder(tree t, int depth){
  if(t == NULL) return;
  inorder(t->left, depth + 1);
  visit(t, depth);
  inorder(t->right, depth + 1);
}

// visit a tree postorder
void postorder(tree t, int depth){
  if(t == NULL) return;
  postorder(t->left, depth + 1);
  postorder(t->right, depth + 1);
  visit(t, depth);
}

// check if a node is an ancestor of a child node
bool is_ancestor(tree ancestor, tree child){
  if(ancestor == NULL) return false;
  if(ancestor == child) return true;
  if(is_ancestor(ancestor->left, child)) return true;
  if(is_ancestor(ancestor->right, child)) return true;
  return false;
}

// find the lowest common ancestor of two nodes given a root
tree least_common_ancestor(tree root, tree node1, tree node2){
  if(root == NULL) return NULL;
  tree tmp = least_common_ancestor(root->left, node1, node2);
  if(tmp != NULL) return tmp;
  tmp = least_common_ancestor(root->right, node1, node2);
  if(tmp != NULL) return tmp;
  if(is_ancestor(root, node1) && is_ancestor(root, node2)) return root;
  return NULL;
}