# Verbose O(n) Java solution using a new Tree with height information

• ``````public class Solution {

class HeightNode {
int val;
int height;
HeightNode left;
HeightNode right;
HeightNode(int val) {
this.val = val;
}
}

private int computeHeights(HeightNode node) {
if(node==null)
return 0;
node.height = 1+Math.max(computeHeights(node.left), computeHeights(node.right));
return node.height;
}

private HeightNode buildHeightNode(TreeNode node) {
if(node==null)
return null;
HeightNode newNode = new HeightNode(node.val);
newNode.left = buildHeightNode(node.left);
newNode.right = buildHeightNode(node.right);
return newNode;
}

private boolean isSame(HeightNode s, HeightNode t) {
if(s==null && t==null)
return true;
else if(s==null || t==null)
return false;
if(s.height != t.height || s.val != t.val)
return false;
return isSame(s.left, t.left) && isSame(s.right, t.right);
}

private boolean helper(HeightNode s, HeightNode t) {
if(t==null)
return true;
if(s==null)
return false;
if(s.height < t.height)
return false;
else if(s.height == t.height)
return s.val != t.val ? false : isSame(s, t);
else
return helper(s.left, t) || helper(s.right, t);
}

public boolean isSubtree(TreeNode s, TreeNode t) {
if(t==null)
return true;
HeightNode ss = buildHeightNode(s);
HeightNode tt = buildHeightNode(t);
computeHeights(ss);
computeHeights(tt);
return helper(ss,tt);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.