Binary Search Tree Contains

找二元搜尋樹裡面的 node。

題目: 給一個值 x，請在 Binary Search Tree 內搜尋有無 x 並回傳該 node，若無則回傳 null。

想法

前幾篇提到有兩種(Depth First, Breadth First)方式可以遍歷(Traversal)整個 Tree， 那在這題情況適合哪一種呢?

想想看，我們的 root node 下來左邊比它自己小，右邊比它自己大，所以只要找其中一邊就好， 那就是 Depth First 會比較適合。

與前一篇 Insert 差不多作法。

底下我們用 recursion 方式來解決此問題。

JavaScript 實作

js

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }

  contains(data) {
    // 若是 root 直接回傳 node
    if(this.data === data){
      return this;
    }

    if (this.data < data && this.right) {
      return this.right.contains(data);
    } else if (this.data > data && this.left) {
      return this.left.contains(data);
    }

    // 上面條件都不符合，回傳 null
    return null;
  }

Java 實作

Java

class BinarySearchTree {

  class Node {
      int key;
      Node left, right;

      public Node(int item) {
          key = item;
          left = right = null;
      }
  }

  Node root;

  BinarySearchTree() {
      root = null;
  }

  public Node contains(Node root, int key) {

  if (root.key==key) {
      return root;
  }

  if (root.key > key){
    return contains(root.left, key);
  } else if (root.key < key){
    return contains(root.right, key);
  }

  return null
  }

}

本文同時發布於鐵人賽