LeetCode: Leaf-similar trees C#

Question

Please comment about performance

https://leetcode.com/problems/leaf-similar-trees/

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.

enter image description here

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Note:

Both of the given trees will have between 1 and 100 nodes.

using System.Collections.Generic;
using GraphsQuestions;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace TreeQuestions
{
 /// <summary>
 /// https://leetcode.com/problems/leaf-similar-trees/
 /// </summary>
 [TestClass]
 public class LeafSimilarTrees
 {
 [TestMethod]
 public void LeafSimilarTreesTest()
 {
 TreeNode root1 = new TreeNode(3);
 root1.left = new TreeNode(5);
 root1.left.left = new TreeNode(6);
 root1.left.right = new TreeNode(2);
 root1.left.right.left = new TreeNode(7);
 root1.left.right.right = new TreeNode(4);
 root1.right = new TreeNode(1);
 root1.right.left = new TreeNode(9);
 root1.right.right = new TreeNode(8);
 TreeNode root2 = new TreeNode(3);
 root2.left = new TreeNode(1);
 root2.left.left = new TreeNode(6);
 root2.left.right = new TreeNode(2);
 root2.left.right.left = new TreeNode(7);
 root2.left.right.right = new TreeNode(4);
 root2.right = new TreeNode(5);
 root2.right.left = new TreeNode(9);
 root2.right.right = new TreeNode(8);
 Assert.IsTrue(LeafSimilar(root1,root2));
 }
 public bool LeafSimilar(TreeNode root1, TreeNode root2)
 {
 List<int> tree1 = new List<int>();
 List<int> tree2 = new List<int>();
 DFS(root1, tree1);
 DFS(root2, tree2);
 if (tree1.Count != tree2.Count)
 {
 return false;
 }
 for (int i = 0; i < tree1.Count; i++)
 {
 if (tree1[i] != tree2[i])
 {
 return false;
 }
 }
 return true;
 }
 public void DFS(TreeNode root, List<int> list)
 {
 if (root == null)
 {
 return;
 }
 if (root.left != null)
 {
 DFS(root.left, list);
 }
 if (root.right != null)
 {
 DFS(root.right, list);
 }
 if (root.left == null && root.right == null)
 {
 list.Add(root.val);
 }
 }
 }
}

Answer 1

There's a problem with your approach: it always visits all nodes to build value lists, even when the trees aren't similar at all. By obtaining leaf-node values lazily, you'll prevent a lot of unnecessary traversal work if the trees are different.

This can be achieved by changing DFS to a generator method (using yield), and comparing the results with SequenceEqual, as janos already pointed out. You'll want to use an explicit stack instead of recursion though, to avoid incurring too much overhead.

However, for trees that are leaf-similar, the added overhead ends up making things slower. The fastest approach is probably a recursive method that does a depth-first traversal of both trees at the same time, bailing out as soon as it finds a leaf-node difference.

• Gilad: Witveot thanks for the code review, sounds very problematic to do that in a coding interview. anyway I like the yield idea thanks!
• Pieter Witvoet: In an interview I would write a general-purpose yield-based traversal method that yields all nodes. Leaf nodes can then easily be selected with a Where(IsLeafNode) call. This results in reusable code that's both readable and still quite performant. I would mention more complex alternatives, and the trade-offs that come with them (expected performance gain versus additional complexity and maintanance, etc.), but only implement them when specifically asked to do so.

Answer 2

In LeafSimilar, you could replace the manual comparison of the list elements with:

return tree1.SequenceEqual(tree2);

In DFS, I would call the parameter node instead of root, to avoid confusion.

• Gilad: SequenceEqual I always forget using that one! thanks Janos