find sub tree

2 files changed, 227 insertions, 0 deletions

diff --git a/2022/08/29/README.md b/2022/08/29/README.md
new file mode 100644
index 0000000..ac96e39
--- /dev/null
+++ b/2022/08/29/README.md
@@ -0,0 +1,36 @@
+Given 2 binary trees `t` and `s`, find if `s` has an equal subtree in `t`,
+where the structure and the values are the same. Return `True` if it
+exists, otherwise return `False`.
+
+Here's some starter code and an example:
+
+```python
+class Node:
+  def __init__(self, value, left=None, right=None):
+    self.value = value
+    self.left = left
+    self.right = right
+  def __repr__(self):
+    return f"(Value: {self.value} Left: {self.left} Right: {self.right})"
+def
+  find_subtree(s, t):
+  # Fill this in.
+t3 = Node(4, Node(3), Node(2))
+t2 = Node(5, Node(4), Node(-1))
+t = Node(1, t2, t3)
+s = Node(4, Node(3), Node(2))
+"""
+Tree t:
+    1
+   / \
+  4   5
+ / \ / \
+3  2 4 -1
+Tree s:
+  4
+ / \
+3  2
+"""
+print(find_subtree(s, t))
+# True
+```
diff --git a/2022/08/29/main.rb b/2022/08/29/main.rb
new file mode 100644
index 0000000..bbced42
--- /dev/null
+++ b/2022/08/29/main.rb
@@ -0,0 +1,191 @@
+#!/usr/bin/env ruby
+
+def assert_equal(x, y)
+  raise "expected: #{x.inspect}, actual: #{y.inspect}" unless x == y
+end
+
+class Node
+  attr_reader :value, :left, :right
+
+  def initialize(value, left = nil, right = nil)
+    @value = value
+    @left = left
+    @right = right
+  end
+
+  def inspect
+    "(#{value}, #{left.inspect}, #{right.inspect})"
+  end
+end
+
+
+def find_subtree(s, t)
+  puts [s&.value, t&.value].inspect if ENV['DEBUG']
+
+  return t.nil? if s.nil?
+  return s.nil? if t.nil?
+
+  if s.value == t.value
+    return find_subtree(s.right, t.right) if s.left.nil?
+    return find_subtree(s&.left, t&.left) if s.right.nil?
+    return find_subtree(s&.left, t&.left) && find_subtree(s.right, t.right)
+  end
+
+  return find_subtree(s, t&.left) || find_subtree(s, t&.right)
+end
+
+
+t = Node.new(
+  1,
+  Node.new(
+    5,
+    Node.new(4),
+    Node.new(-1)
+  ),
+  Node.new(
+    4,
+    Node.new(3),
+    Node.new(2)
+  )
+)
+s = Node.new(
+  4,
+  Node.new(3),
+  Node.new(2)
+)
+
+assert_equal(true, find_subtree(s, t))
+
+t = Node.new(
+  1,
+  Node.new(
+    5,
+    Node.new(4),
+    Node.new(-1)
+  ),
+  Node.new(
+    4,
+    Node.new(3),
+    Node.new(2)
+  )
+)
+s = Node.new(
+  5,
+  Node.new(4),
+  Node.new(-1)
+)
+assert_equal(true, find_subtree(s, t))
+
+t = Node.new(
+  1,
+  Node.new(
+    5,
+    Node.new(4),
+    Node.new(-1)
+  ),
+  Node.new(
+    4,
+    Node.new(3),
+    Node.new(2)
+  )
+)
+s = Node.new(3)
+assert_equal(true, find_subtree(s, t))
+
+t = Node.new(
+  1,
+  Node.new(
+    5,
+    Node.new(4),
+    Node.new(-1)
+  ),
+  Node.new(
+    4,
+    Node.new(3),
+    Node.new(2)
+  )
+)
+s = Node.new(2)
+assert_equal(true, find_subtree(s, t))
+
+t = Node.new(
+  1,
+  Node.new(
+    5,
+    Node.new(4),
+    Node.new(-1)
+  ),
+  Node.new(
+    4,
+    Node.new(3),
+    Node.new(2)
+  )
+)
+s = Node.new(
+  1,
+  Node.new(
+    5,
+    Node.new(4),
+    Node.new(-1)
+  ),
+  Node.new(
+    4,
+    Node.new(3),
+    Node.new(2)
+  )
+)
+assert_equal(true, find_subtree(s, t))
+
+t = Node.new(
+  1,
+  Node.new(
+    5,
+    Node.new(4),
+    Node.new(-1)
+  ),
+  Node.new(
+    4,
+    Node.new(3),
+    Node.new(2)
+  )
+)
+s = Node.new(
+  1,
+  Node.new(
+    5,
+    nil,
+    Node.new(-1)
+  ),
+)
+assert_equal(true, find_subtree(s, t))
+
+
+t = Node.new(
+  1,
+  Node.new(
+    5,
+    Node.new(4),
+  ),
+  Node.new(
+    4,
+    Node.new(3),
+    Node.new(2)
+  )
+)
+s = Node.new(
+  1,
+  Node.new(
+    5,
+    Node.new(4),
+    Node.new(-1)
+  ),
+  Node.new(
+    4,
+    Node.new(3),
+    Node.new(2)
+  )
+)
+
+assert_equal(false, find_subtree(s, t))
+
+assert_equal(false, find_subtree(nil, t))