Excerpt
# Tree
Ruby has no built-in class for initializing Binary Tree data structure. Tree is just a restricted form of a Graph which have a parent-child relationship.
Here is the simplest definition for a binary tree node:
```plain text
class Node
attr_accessor :val, :left, :right
def initialize(val)
@val = val
@left,@right = nil, nil
end
end
```
Let’s build a tree as an example:
```plain text
root = Node.new(3)child_l = Node.new(9)
child_r = Node.new(20)grand_child_r_l = Node.new(15)
grand_child_r_r = Node.new(7)
grand_child_l_l = Node.new(33)child_r.left = grand_child_r_l
child_r.right = grand_child_r_r
child_l.left = grand_child_l_lroot.right = child_r
root.left = child_l
```
This tree can be illustrated by the image below.
# DFS (Depth-first search)
```plain text
def dfs(node)
p node.val children =[node.left, node.right].compact children.each do |child|
dfs(child)
end
enddfs(root)
```
O
# Tree
Ruby has no built-in class for initializing Binary Tree data structure. Tree is just a restricted form of a Graph which have a parent-child relationship.
Here is the simplest definition for a binary tree node:
```plain text
class Node
attr_accessor :val, :left, :right
def initialize(val)
@val = val
@left,@right = nil, nil
end
end
```
Let’s build a tree as an example:
```plain text
root = Node.new(3)child_l = Node.new(9)
child_r = Node.new(20)grand_child_r_l = Node.new(15)
grand_child_r_r = Node.new(7)
grand_child_l_l = Node.new(33)child_r.left = grand_child_r_l
child_r.right = grand_child_r_r
child_l.left = grand_child_l_lroot.right = child_r
root.left = child_l
```
This tree can be illustrated by the image below.
# DFS (Depth-first search)
```plain text
def dfs(node)
p node.val children =[node.left, node.right].compact children.each do |child|
dfs(child)
end
enddfs(root)
```
Output is next:
```plain text
3
9
33
20
15
7
```
DFS algorithm starts with root node then explores each node in-depth, then goes to the next node and does the same until it goes around the whole tree.
# BFS (Breadth-first search)
```plain text
def bfs(node)
queue = []
queue.push(node) while(queue.size != 0)
node = queue.shift
p node.val children = [node.left, node.right].compact children.each do |child|
queue.push(child)
end
end
endbfs(root)
```
Result:
```plain text
3
9
20
33
15
7
```
BFS algorithm also starts with root node, but unlike with the DFS algorithm, here we took each value on the same level of depth.
# Maximum Depth of Binary Tree
Let’s consider small task solved through DFS.
```plain text
Given the root of a binary tree, returnits maximum depth.A binary tree'smaximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
```
Given an example B-tree:
Ruby Solution
```plain text
def max_depth(root)
return 0 if root.nil? queue = [root]
depth = 0 while !queue.empty?
for i in 0..queue.length - 1
node = queue.shift
queue.push(node.left) if node.left
queue.push(node.right) if node.right
end depth += 1
end depth
end
```
Here we are calculating depth by incrementing the variable for each breadth iteration.