Interview Questions

  • View all interview questions
  • blank
  • Determine if binary tree is a subtree of a larger binary tree
    In a previous algorithm tutorial we discussed how to traverse a tree using different algorithms. Now we'll solve a popular tree algorithm question of determining if a binary tree is a subtree within a larger tree. In the picture below, you can see that the tree on the left is contained within the tree on the right, underneath the gray node with a value of 10.


    You need to be a premium member to see the rest of this question and code.

    Become a Premium Member

    With our large collection of challengs, tutorials, and solutions, we make it easy for you to become a better coder, prepare for interviews, and learn new skills from more experienced coders.

    “If you're able to solve Medium Coderbyte problems and have a good understanding of web development basics [...] then you are probably ready for admissions at the top schools.” ― Huntly Mayo-Malasky
    • 200+ Coding Challenges
    • Mock Interview Questions
    • 500,000+ Code Solutions
    • Algorithm Tutorials
    • Interview Prep Courses
    mrdaniel published this on 6/11/16 | tree, traversal, subtree
    Comments
  • +
  • 0
  • -
  • @mhelvens, The example you provided produces the following traversal arrays on the trees: inorder: [2, 1, 3] [3, 2, 1, 0, 1, 2, 3] preorder: [1, 2, 3] [0, 1, 2, 3, 1, 2, 3] You can see that in the preorder traversal the smaller array does in fact exist within the larger array, but for the inorder arrays, that is not the case. [2, 1, 3] is not contained in [3, 2, 1, 0, 1, 2, 3]. So this wouldn't produce a false positive because the is_subtree function will return false.
  • +
  • 0
  • -
  • This algorithm is incorrect. It can produce false positives if the `inord` match and the `preord` match occur in unrelated parts of the original tree.
    // smaller tree
    //
    var root = new Node(1);
    var n2 = new Node(2);
    var n3 = new Node(3);
    //
    root.left  = n2;
    root.right = n3;
    
    // larger tree
    var root_r = new Node(0);
    var n_l1 = new Node(1);
    var n_l2 = new Node(2);
    var n_l3 = new Node(3);
    var n_r1 = new Node(1);
    var n_r2 = new Node(2);
    var n_r3 = new Node(3);
    //
    root_r.left = n_l1;
    n_l1.left = n_l2;
    n_l2.left = n_l3
    root_r.right = n_r1;
    n_r1.right = n_r2;
    n_r2.right = n_r3;
    
    Login to submit a comment