235. Lowest common ancestor

235_solution1.c

#include "tree_node.h"

struct TreeNode *lowestCommonAncestor(struct TreeNode *root, struct TreeNode *p,
                                      struct TreeNode *q) {
  if (p->val > q->val)
    return lowestCommonAncestor(root, q, p);

  while (root) {
    if (root->val >= p->val && root->val <= q->val)
      return root;

    if (root->val < p->val)
      root = root->right;
    else
      root = root->left;
  }

  return root;
}

235_solution2.c

#include "tree_node.h"

struct TreeNode *lowestCommonAncestor(struct TreeNode *root, struct TreeNode *p,
                                      struct TreeNode *q) {
  if (p->val > q->val)
    return lowestCommonAncestor(root, q, p);

  if (root->val >= p->val && root->val <= q->val)
    return root;

  if (q->val < root->val)
    return lowestCommonAncestor(root->left, p, q);
  else
    return lowestCommonAncestor(root->right, p, q);
}

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

235_solution1.cpp

#include "tree_node.h"

class Solution {
public:
  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (p->val > q->val)
      return lowestCommonAncestor(root, q, p);

    while (root) {
      if (root->val >= p->val && root->val <= q->val)
        return root;

      if (root->val < p->val)
        root = root->right;
      else
        root = root->left;
    }

    return root;
  }
};

235_solution2.cpp

#include "tree_node.h"

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
  TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
    if (p->val > q->val)
      return lowestCommonAncestor(root, q, p);

    if (root->val >= p->val && root->val <= q->val)
      return root;

    if (q->val < root->val)
      return lowestCommonAncestor(root->left, p, q);
    else
      return lowestCommonAncestor(root->right, p, q);
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

235_solution1.go

package trees

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if p.Val > q.Val {
        return lowestCommonAncestor(root, q, p)
    }

    for root != nil {
        if root.Val >= p.Val && root.Val <= q.Val {
            return root
        }

        if root.Val < p.Val {
            root = root.Right
        } else {
            root = root.Left
        }
    }

    return root
}

235_solution2.go

package trees

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    if p.Val > q.Val {
        return lowestCommonAncestor(root, q, p)
    }

    if root.Val >= p.Val && root.Val <= q.Val {
        return root
    }

    if q.Val < root.Val {
        return lowestCommonAncestor(root.Left, p, q)
    }
    return lowestCommonAncestor(root.Right, p, q)
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

235_solution1.java

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val > q.val)
            return lowestCommonAncestor(root, q, p);

        while (root != null) {
            if (root.val >= p.val && root.val <= q.val)
                return root;

            if (root.val < p.val)
                root = root.right;
            else
                root = root.left;
        }

        return root;
    }
}

235_solution2.java

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (p.val > q.val)
            return lowestCommonAncestor(root, q, p);

        if (root.val >= p.val && root.val <= q.val)
            return root;

        if (q.val < root.val)
            return lowestCommonAncestor(root.left, p, q);
        else
            return lowestCommonAncestor(root.right, p, q);
    }
}

TreeNode.java

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

235_solution1.js

const TreeNode = require("./tree_node");

var lowestCommonAncestor = function (root, p, q) {
  if (p.val > q.val) return lowestCommonAncestor(root, q, p);

  while (root) {
    if (root.val >= p.val && root.val <= q.val) return root;

    if (root.val < p.val) root = root.right;
    else root = root.left;
  }

  return root;
};

235_solution2.js

const TreeNode = require("./tree_node");

var lowestCommonAncestor = function (root, p, q) {
  if (p.val > q.val) return lowestCommonAncestor(root, q, p);

  if (root.val >= p.val && root.val <= q.val) return root;

  if (q.val < root.val) return lowestCommonAncestor(root.left, p, q);
  else return lowestCommonAncestor(root.right, p, q);
};

tree_node.js

// Definition for a binary tree node.
function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

module.exports = TreeNode;

235_solution1.py

from tree_node import TreeNode


class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if p.val > q.val:
            return self.lowestCommonAncestor(root, q, p)

        while root:
            if p.val <= root.val <= q.val:
                return root

            if root.val < p.val:
                root = root.right
            else:
                root = root.left

        return root

235_solution2.py

from tree_node import TreeNode


class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        if p.val > q.val:
            return self.lowestCommonAncestor(root, q, p)

        if p.val <= root.val <= q.val:
            return root

        if q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        else:
            return self.lowestCommonAncestor(root.right, p, q)

tree_node.py

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

235_solution1.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

impl Solution {
    pub fn lowest_common_ancestor(
        root: Option<Rc<RefCell<TreeNode>>>,
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        let (mut pv, mut qv) = (p?.borrow().val, q?.borrow().val);
        if pv > qv {
            std::mem::swap(&mut pv, &mut qv);
        }

        let mut cur = root;
        while let Some(node) = cur {
            let val = node.borrow().val;
            if val >= pv && val <= qv {
                return Some(node);
            }

            if val < pv {
                cur = node.borrow().right.clone();
            } else {
                cur = node.borrow().left.clone();
            }
        }

        None
    }
}

235_solution2.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

impl Solution {
    pub fn lowest_common_ancestor(
        root: Option<Rc<RefCell<TreeNode>>>,
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        let (pv, qv) = (p.as_ref()?.borrow().val, q.as_ref()?.borrow().val);
        if pv > qv {
            return Self::lowest_common_ancestor(root, q, p);
        }

        let node = root?;
        let val = node.borrow().val;
        if val >= pv && val <= qv {
            return Some(node);
        }

        let next = if qv < val {
            node.borrow().left.clone()
        } else {
            node.borrow().right.clone()
        };
        Self::lowest_common_ancestor(next, p, q)
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}