Depth First Search

Giriş
Depth First Search (DFS) sürekli alt seviyeye giderek tüm çocukları dolaşır. 

DFS Iterative veya Recursive olarak gerçekeleştirilebilir

1. Iterative Algoritma
DFS'in algoritması şöyledir.

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v = S.pop() 
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

Örnek
Şöyle yaparız.

static bool Contains<T>(T item, Node<T> tree) {
  Stack<Node<T>> stack = new Stack<Node<T>>();

  stack.Push(tree); //Push the root node into the stack

  Node<T> current;
  do {
    current = stack.Pop(); //Get the last item 

    if (item.Equals(current.Data))
    {
      Console.WriteLine("Found");
      return true; //then return true
    }

    //Otherwise add the left and right nodes to the stack if they exist.
    if(current.Left != null)
      stack.Push(current.Left);
    if(current.Right != null)
      stack.Push(current.Right);
  } while(stack.Count > 0); //If the stack still contains items, go back to the 'do'

  //If we've reached this point we've searched the entire tree and found nothing
  return false;
}

2. Düğümün İşlenmesi
DFS'i gerçekleştirmek için 3 tane yöntem var. Ziyaret edilen düğüm hemen işleniyorsa Pre-Order denilir. İşleme In-Order, Post-Order olarak ta yapılabilir. Pre-Order dışında hiçbirini kullanmadım.

1. Pre-Order
Açıklaması şöyle. Düğüm ziyaret edilince hemen bir iş yapılır.

Do a depth-first traveral and write out the node when you encounter it the first time.

Örnek - recursive dolaşarak range içindekileri bulma

Elimizde bir fiyat ağacı olsun. low ve high arasındaki ürünleri bulmak için şöyle yaparız.

- Eğer low değeri düğümün sol tarafından halen küçükse sol taraf dolaşılır. 

- Eğer düğümün sağ tarafı high değerinden küçükse sağ taraf ta dolaşılır

- low = 7, high = 20 ise çıktı olarak {9, 8, 14, 20, 17} alırız

public static void preOrder(Node node, int low, int high, List<Integer> output){
  if (node != null) {
    if (node.val <= high && low <= node.val)
      output.add(node.val);
    if (low <= node.val)
      preOrder(node.leftChild, low, high, output);
    if (node.val <= high)
      preOrder(node.rightChild, low, high, output);
  }
}

public static List<Integer> productsInRange(Node root, int low, int high){
  List<Integer> output = new ArrayList<>();
  preOrder(root, low, high, output);
  return output;
}

public static void main( String args[] ) {
  // Driver code
  BinarySearchTree bst = new BinarySearchTree();
  bst.insert(9);
  bst.insert(6);
  bst.insert(14);
  bst.insert(20);
  bst.insert(1);
  bst.insert(30);
  bst.insert(8);
  bst.insert(17);
  bst.insert(5);
  System.out.println(productsInRange(bst.root, 7, 20));
}

2. Post-Order
Açıklaması şöyle

Do a depth-first traversal and write out the node after you have processed all its children.

3. In-Order
Açıklaması şöyle. 

Do a depth-first traversal and write out the left subtree first, then the node itself and afterwards the right subtree. 

Klasik bir  In-Order kodu şöyledir

private void inOrder(TreeNode node) {
  if (node == null) {
    return;
  }
  inOrder(node.left);
  System.out.printf("%s ", node.data); //Burası In-Order'da yapılan iş
  inOrder(node.right);
}

Örnek
Elimizde şöyle bir ağaç olsun. Bu ağacı şöyle dolaşırsak in-order olur. 12, 25, 37, 50, 75, 62, 85

                          50
                         /  \
                        /    \
                       /      \
                     25        75
                    /  \      /  \
                  12    37  62    85

Örnek

Elimizde şöyle bir ağaç olsun. Ağaç sıralı bir binary tree değil.

                                     9
                                  /     \
                                 5       12
                                / \     /  \
                               2   7   11   15
                              /   /   /  \    \
                             3   6   10  13    16
                                                 \
                                                  17

Bu ağacın dolaşması şöyledir.

pre-order: 9 5 2 3 7 6 12 11 10 13 15 16 17
post-order: 3 2 6 7 5 10 13 11 17 16 15 12 9
in-order: 3 2 5 6 7 9 10 11 13 12 15 16 17

3. Çeşitli Sorular

Bu sorular iterative veya recursive çözülebilir.

Binary Tree Node Count
Ağaçtaki toplam düğüm sayısı bulunur.

Örnek - recursive
Şöyle yaparız.

int count(node *tree)
{
  int c =  1;             //Node itself should be counted
  if (tree ==NULL)
    return 0;
  else
  {
    c += count(tree->left);
    c += count(tree->right);
    return c;
  }
}

Örnek - recursive
Şöyle yaparız.

int count(Node root) {
  if (root != null) {
    return 1 + count(root.left) + count(root.right);
  } else {
    return 0;
  }
}

İki Binary Tree'nin Eşit Olması
İmzasını şöyle  yaparız.

bool checkSame(Node* first, Node* second);

İçi şöyledir.

return first->data == second->data 
    && checkSame(first->left, second->left)
    && checkSame(first->right, second->right);

Binary Tree Leaves 
Elimizde şöyle bir soru olsun.

Given the preorder traversal of a binary search tree, how do we identify the leaf nodes without building the tree?

Düğümler şöyle olsun

[5,3,2,4,8,7,9]

Her düğümün iki çocuğu olduğunu varsayarsak ve pre-order dolaştığımızı tersten başlarız ve graph'ı şu hale getiririz.

[*,*,2,4,*,7,9]

Binary Tree Depth
Ağacın derinliği bulunur

Örnek - recursive
Şöyle yaparız.

public int maxDepth(TreeNode root) {

   if(root == null)
    return 0;

  int left = maxDepth(root.left);
  int right = maxDepth(root.right);

  if(left > right)
    return left + 1;
  else
    return right + 1;
}

İkinci If'ten kurtulmak için şöyle yaparız.

public int maxDepth(TreeNode root) {
  if (root == null) {
    return 0;
  }
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

Binary Tree Balanced 
Şöyle yaparız.

public static int getHeight(Node root) {
  if (root == null) return -1;
  return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

public static boolean isBalanced(Node root) {
  if (root == null) return true;

  int heightDiff = getHeight(root.left) - getHeight(root.right);
  if (Math.abs(heightDiff) > 1) {
    return false;
  } else {
    return isBalanced(root.left) && isBalanced(root.right);
  }
}

Topological Sort

Birbirine bağlı olan işler için kullanılır.Şöyle yaparız.

result = []
visited = {}
dfs(x):
  if x in visited: return
  visited.insert(x)
  for y in adj(x):
    dfs(y)
  result.push(x)
for x in V: dfs(x)
reverse(result)

Açıklaması şöyle

If a topological sort has the property that all pairs of consecutive vertices in the sorted order are connected by edges, then the topological sort order is unique.

Örnek
Elimizde şu işler olsun.

A1, B, C1, A2, A3, F, G, C2, H, A4

Sonucun şöyle olmasını isteyelim. Yani önce C'ler yapılacak, en son B'ler yapılacak. Aradaki işlerin sırası korunacak.

C1 C2 A1 A2 A3 F G H A4 B

Şöyle yaparız.

template <typename Iterator, typename Compare>
void stable_toposort(Iterator begin, Iterator end, Compare cmp)
{
 while (begin != end)
 {
   auto const new_begin = std::stable_partition(begin, end, [&](auto const& a)
   {
     return std::none_of(begin, end, [&](auto const& b) { return cmp(b, a); });
    });
    assert(new_begin != begin && "not a partial ordering");
    begin = new_begin;
  }
}

Comparator şöyledir. stable_partition() ile elemanları kendi içinde gruplarız ve gruplama tüm elemanlar bitinceya kadar devam eder. Önce C ve A'ları gruplarız. Daha sonra A ve B'leri gruplarız.

bool CompareItems(SItem const& item1, SItem const& item2)
{
 if (item1.type == C && item2.type == A) return true;
 if (item1.type == A && item2.type == B) return true;
 return false;
}