Lowest Common Ancestor for a Binary Tree

lowestCommAnc.go

/*
Algorithm
- if a node is NULL or equal p or q, we return it
- if not, we traverse the left and right subtree until we return a node, assigning to bool value RetLeft or RetRight
- Then we check if we have to return the node (RetLeft and RetRight are both != NULL), or only left or right
- The LCA is of course the node with RetLeft AND RetRight != NULL
*?

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	
    if (root == nil || root == p || root == q) {
		return root
	}

	RetLeft := lowestCommonAncestor(root.Left, p, q)
	RetRight := lowestCommonAncestor(root.Right, p, q)
	
    if (RetLeft != nil && RetRight != nil) {
		return root
	}
	if RetLeft != nil {
		return RetLeft
	}
	return Retright
}