You can consider it as a tree, but it's usually not a tree in the conventional data structures sense. It's almost always of a constant depth, and so is, in fact O(1). The vast majority of Redux states look something like this:

  {
    todos: {
      1: {},
      2: {},
      ...
    }
  }

And so all references are O(1). Real applications often have much bigger and more complicated structures, but they're nearly always of constant depth.