Skip to main content

Binary Trees

Trees

Binary trees are widely used data structures. Similar to linked lists, they are inductively defined: a binary tree node is comprised of a value and two child binary tree nodes, left and right. A binary tree can also be empty. The node that a child of no subtree is called the root. Binary trees are most useful in contexts where data has some kind of ordering since one can put the lesser nodes (with respect to a given node) on the left and the greater ones on the right. Binary trees tend to show up quite a bit in interviews because there are a lot of interesting problems you can ask about them. The key concept you need to learn is the many ones one can traverse a binary tree.

Tree in programming are more like family trees (without accounting for marriages) in that they grow downward. A diagram that lists your great great grandparent and all descendants would be a good example.

Consider the following binary tree:

       1
      / \
     2   3
    / \   \
   4   5   6
The four most prevalent traversal orders are:
  1. Preorder: 1 2 4 5 3 6
  2. Inorder: 4 2 5 1 3 6
  3. Postorder: 4 5 2 6 3 1
  4. Level order: 1 2 3 4 5 6

There is some basic terminology you need to have down cold:

  1. root: The node from which a binary tree emanates. It has no parent and all nodes in the tree are descendants of the root. Usually, we supply a root to a function to pass it the tree since you can access all the tree from the root.
  2. leaf: A node in a tree that has no children. Leaves from the bottom edge of a tree.
  3. subtree: A contiguous component of a tree consisting of a root of the subtree and all its descendants.
  4. descendant: a node B is said to be a descendant of another node A if one can reach B by following the child pointers from A and its children, descendants, etc.

Binary Tree Problems

  1. Let's extend the binary tree definition with a fourth member, next, which will be a pointer to the adjacent sibling of a given node. Given the root of a binary tree with all the next members nulled out, write a function that fills in all the next members. For the rightmost side of the tree, the next member for each node should be null. So, for the following input:

           1
          / \
         2   3
        / \   \
       4   5   6
    
    Your function should produce the following output:
           1 -> null
          / \ 
         2-> 3 -> null
        / \   \
       4 ->5-> 6 -> null 
    
  2. A binary tree is said to be symmetric if the left subtree from the root is the mirror of the right subtree in terms of both values and structure. Write a function that determines if a binary tree is symmetric.
  3. The lowest common ancestor (LCA) of two nodes in a tree is the node furthest from the root that is an ancestor of both nodes. Write a function that takes a tree and two nodes in that node as input. The function should return the LCA of the two nodes.

We still need to wrap up the list addition problem and stack and queue problems. Remember to practice these problems by using the procedural given in the problem solving checklist including doing a basic running time and space analysis.

Check out the local tech job openings in Chicago when you get a chance.

Comments

  1. Hi,

    Its Mo here.

    I have managed to complete number 3 if we assume that the tree is a BST, rather than an ordinary binary tree. I tried applying a similar algorithm, tweaking the path traversal, however I am still missing something.

    Am I allowed to post code here?

    ReplyDelete
    Replies
    1. I would hold off just a bit. Let's give everyone a chance to come up with a few approaches. Thanks!

      Delete
  2. Its Nadiia.
    I solved number 3 for a binary tree

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
    Replies
    1. For those of you who requested that I share my code for #1 above, here it is:

      Note: the indentation appears to be off, even though before I post the comment, it appears to be correct. Not sure what I can do about this.

      '''

      /**
      * Definition for binary tree with next pointer.
      * public class TreeLinkNode {
      * int val;
      * TreeLinkNode left, right, next;
      * TreeLinkNode(int x) { val = x; }
      * }
      */

      public class Solution
      {
      public void connect(TreeLinkNode root)
      {
      if (root == null || (root.left == null && root.right == null)) return;// if node is null or if node is leaf node
      TreeLinkNode current = root;
      if (root.left != null && root.right != null)
      {
      root.left.next = root.right;// connecting left child to right child
      // connecting right child
      if (current.next == null) root.right.next = null;
      else
      {
      while (current.next != null)
      {
      current = current.next;
      if (current.left == null && current.right == null) continue;
      else if (current.left != null)
      {
      root.right.next = current.left;
      break;
      }
      else if (current.right != null)
      {
      root.right.next = current.right;
      break;
      }
      }
      }
      }
      else if (root.left == null && root.right != null)//connecting right child
      {
      if (current.next == null) root.right.next = null;
      else
      {
      while (current.next != null)
      {
      current = current.next;
      if (current.left == null && current.right == null) continue;
      else if (current.left != null)
      {
      root.right.next = current.left;
      break;
      }
      else if (current.right != null)
      {
      root.right.next = current.right;
      break;
      }
      }
      }
      }
      else if (root.left != null && root.right == null)//connecting left child
      {
      while (current.next != null)
      {
      current = current.next;
      if (current.left == null && current.right == null) continue;
      else if (current.left != null)
      {
      root.left.next = current.left;
      break;
      }
      else if (current.right != null)
      {
      root.left.next = current.right;
      break;
      }
      }
      }
      connect(root.right);
      connect(root.left);
      }
      }
      '''

      Delete
    2. This comment has been removed by the author.

      Delete

Post a Comment

Popular posts from this blog

Top 5 Books for Language-Specific Interview Questions

Shrunk and White of Programming When you put down that you know a certain programming language or languages on your resume, you are setting certain expectations for the interviewer. I would strongly caution against putting down "expert" in a language unless you invented or are one of the language's maintainers. You are giving your interviewer the license to quiz you on programming language lore. There are a handful of concepts that are considered "standard" knowledge for each language which go broadly beyond syntax and general semantics. These concepts commonly involve major pitfalls in a given language and the idiomatic technique for negotiating these pitfalls and writing efficient and maintainable code. Note, although the concepts are considered idiomatic, you can seldom infer them from knowledge of syntax and semantics alone. The tricky part here is that most courses that teach a particular programming language do not cover these idiomatic techniques and eve…

Interview Gotchas

It's a challenge to outperform all the other candidates in a competitive tech job only, but there is hope. You can improve your performance with practice and watching out for these gotchas: Make absolutely sure you are solving the right problem: I ran into this the other day. It is entirely a communication issue. When doing an initial screen over the phone, this problem is compounded. For example, maybe an interviewee is hacking out a function that returns the k highest priced products when the interviewer is expecting the kth highest priced product. One can squander a lot of time due to these misunderstandings. A good interviewer will try to guide you back to the right path, but you can't expect this. Be sure to ask questions. Confirm that the input and output are exactly what you expect. Use examples.Don't ever give an interviewer the impression that you are avoiding writing real code. This is an impression thing. This is a coding interview so you should be expecting to…

Complexity Analysis for Interviews, Part 1

This is part 1 of a two part series. Skip over to part 2 you'd like . For coding interviews, we are interested in gauging the asymptotic efficiency of algorithms both in terms of running time and space. The formal study of analysis of algorithms is called complexity theory, a rich field with fascinating and complicated math. For interviews, we only need a few basic concepts. Asymptotic efficiency is concerned with how the running time or memory requirements of an algorithm grows with the input size, so it is intimately concerned with how well algorithms scale to larger inputs. This is important in Computer Science and in practice because whereas some algorithms work well enough for small inputs of say < 10 inputs, the running time and space grows far faster than the input size and thus large inputs of say 10s to millions of inputs becomes impractical (usually meaning taking hours or even years of execution time). Consider sorting. Say for the sake of argument that sorting alg…